Find the maximum value of `j – i` such that `A[j] > A[i]` in an array
Given an integer array nums, find the maximum value of j-i such that nums[j] > nums[i].
For example,
Output: 5
Explanation: The maximum difference is 5 for i = 0, j = 5
Input: [9, 2, 1, 6, 7, 3, 8]
Output: 5
Explanation: The maximum difference is 5 for i = 1, j = 6
Input: [8, 7, 5, 4, 2, 1]
Output: -INF
Explanation: Array is sorted in decreasing order.
1. Brute-Force Solution
A simple solution is to use two loops. For each element, check the greater elements to its right and keep track of the maximum value of j-i. The time complexity of this solution is O(n2), where n is the size of the input.
Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <vector> #include <limits> using namespace std; // Function to find the maximum value of `j-i` such that nums[j] > nums[i] int findMaxDiff(vector<int> const &nums) { int n = nums.size(); int diff = numeric_limits<int>::min(); // base case if (n == 0) { return diff; } for (int i = 0; i < n; i++) { for (int j = n - 1; j > i; j--) { if (nums[j] > nums[i] && diff < j - i) { diff = j - i; break; } } } return diff; } int main() { vector<int> nums = { 9, 10, 2, 6, 7, 12, 8, 1 }; cout << "The maximum value is " << findMaxDiff(nums) << endl; return 0; } |
Output:
The maximum value is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Main { // Function to find the maximum value of `j-i` such that nums[j] > nums[i] public static int findMaxDiff(int[] nums) { int diff = Integer.MIN_VALUE; // base case if (nums == null || nums.length == 0) { return diff; } for (int i = 0; i < nums.length; i++) { for (int j = nums.length - 1; j > i; j--) { if (nums[j] > nums[i] && diff < j - i) { diff = j - i; } } } return diff; } public static void main(String[] args) { int[] nums = { 9, 10, 2, 6, 7, 12, 8, 1 }; System.out.println("The maximum value is " + findMaxDiff(nums)); } } |
Output:
The maximum value is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import sys # Function to find the maximum value of `j-i` such that nums[j] > nums[i] def findMaxDiff(nums): diff = -sys.maxsize # base case if not nums: return diff for i in range(len(nums)): for j in reversed(range(i + 1, len(nums))): if nums[j] > nums[i] and diff < j - i: diff = j - i return diff if __name__ == '__main__': nums = [9, 10, 2, 6, 7, 12, 8, 1] print('The maximum value is', findMaxDiff(nums)) |
Output:
The maximum value is 5
2. O(n) solution using extra space
The idea is to construct an auxiliary array aux, where aux[j] stores the maximum element in subarray nums[j…n-1]. Then traverse the auxiliary array aux from left to right along with the input array nums to find the greatest j-i value, as demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <vector> #include <limits> using namespace std; // Function to find the maximum value of `j-i` such that nums[j] > nums[i] int findMaxDiff(vector<int> const &nums) { // `diff` stores the maximum value of `j-i` such that nums[j] > nums[i] int diff = numeric_limits<int>::min(); int n = nums.size(); // base case if (n == 0) { return diff; } // create an auxiliary array of size `n` int aux[n]; // aux[j] stores the maximum element in subarray nums[j, n-1] aux[n - 1] = nums[n - 1]; for (int j = n - 2; j >= 0; j--) { aux[j] = max(nums[j], aux[j + 1]); } // Find maximum `j-i` using the auxiliary array for (int i = 0, j = 0; i < n && j < n; ) { if (nums[i] < aux[j]) { diff = max(diff, j - i); j++; } else { i++; } } return diff; } int main() { vector<int> nums = { 9, 10, 2, 6, 7, 12, 8, 1 }; cout << "The maximum value is " << findMaxDiff(nums) << endl; return 0; } |
Output:
The maximum value is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Main { // Function to find the maximum value of `j-i` such that nums[j] > nums[i] public static int findMaxDiff(int[] nums) { // `diff` stores the maximum value of `j-i` such that nums[j] > nums[i] int diff = Integer.MIN_VALUE; // base case if (nums == null || nums.length == 0) { return diff; } int n = nums.length; // create an auxiliary array of size `n` int[] aux = new int[n]; // aux[j] stores the maximum element in subarray nums[j, n-1] aux[n - 1] = nums[n - 1]; for (int j = n - 2; j >= 0; j--) { aux[j] = Integer.max(nums[j], aux[j + 1]); } // Find maximum `j-i` using the auxiliary array for (int i = 0, j = 0; i < n && j < n; ) { if (nums[i] < aux[j]) { diff = Integer.max(diff, j - i); j++; } else { i++; } } return diff; } public static void main(String[] args) { int[] nums = { 9, 10, 2, 6, 7, 12, 8, 1 }; System.out.println("The maximum value is " + findMaxDiff(nums)); } } |
Output:
The maximum value is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import sys # Function to find the maximum value of `j-i` such that nums[j] > nums[i] def findMaxDiff(nums): # `diff` stores the maximum value of `j-i` such that nums[j] > nums[i] diff = -sys.maxsize # base case if not nums: return diff # get the length of the array n = len(nums) # create an auxiliary array of size `n` aux = [0] * n # aux[j] stores the maximum element in subarray nums[j, n-1] aux[n - 1] = nums[n - 1] for j in reversed(range(n - 1)): aux[j] = max(nums[j], aux[j + 1]) # Find maximum `j-i` using the auxiliary array i = j = 0 while i < n and j < n: if nums[i] < aux[j]: diff = max(diff, j - i) j += 1 else: i += 1 return diff if __name__ == '__main__': nums = [9, 10, 2, 6, 7, 12, 8, 1] print('The maximum value is', findMaxDiff(nums)) |
Output:
The maximum value is 5
The time complexity of the above solution is O(n), and the auxiliary space used by the program is O(n).
Find the maximum absolute difference between the sum of two non-overlapping subarrays
Find the minimum and maximum element in an array using Divide and Conquer
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)