Find maximum j – i such that X[j] > X[i]
Difficulty: Medium, Asked-in: Amazon, Google, Adobe, Hike
Key takeaway: An excellent problem to learn problem-solving using sorting, extra memory, and two-pointers approaches.
Let’s understand the problem!
Given an unsorted array X[] of distinct elements, write a program to find the maximum difference between a pair of indices such larger value appears after the element with the smaller value i.e. j > i and X[j] > X[i]. Assume that all values in the input are distinct. Note: There can be several such pairs of indices for which the difference will be maximum. We just need to return the max difference between j - i.
Example 1
Input: X[] = [40, 20, 70, 10, -20, 80, 30, -10], Output = 5
Explanation: There are two such pairs with maximum index difference: (40, 80) and (20, 30). Index difference between (40, 80) = 5 - 0 = 5, and index difference between (20, 30) = 6 - 1 = 5.
Example 2
Input: X[] = [1, 2, 3, 4, 5, 6], Output = 5
Explanation: Array is sorted in increasing order. So the max difference between the first and last index will be the maximum of j - i.
Example 3
Input: X[] = [7, 6, 5, 4, 3, 2], Output = -1
Explanation: Array is sorted in decreasing order. So no such max difference exists in the array.
Discussed solution approaches
- Brute force approach using nested loops
- Using extra memory and binary search
- Using sorting: Sorting (element, index) pairs in increasing order
- Efficient approach using extra memory and two-pointers
Brute force approach using nested loops
Solution idea
A basic idea would be to explore every pair of indices (j > i) using nested loops. If (X[j] > X[i]), we update the max difference i.e. if(X[j] > X[i]), maxDiff = max (maxDiff, j - i).
Here we pick the first index using the outer loop (i = 0 to n - 2) and the second index using the inner loop (j = i + 1 to n - 1). This loop structure ensures that the value of j is always greater than i.
Solution code C++
int maxIndexDiff(int X[], int n)
{
int maxDiff = -1;
for(int i = 0; i < n - 1; i = i + 1)
{
for(int j = i + 1; j < n; j = j + 1)
{
if(X[j] > X[i])
maxDiff = max(maxDiff, j - i);
}
}
return maxDiff;
}Solution code Python
def maxIndexDiff(X):
n = len(X)
maxDiff = -1
for i in range(n - 1):
for j in range(i + 1, n):
if X[j] > X[i]:
maxDiff = max(maxDiff, j - i)
return maxDiffTime and space complexity analysis
We explore every possible pair of indices using a nested loop and perform constant operations at each iteration. Total number of pairs = nC2 = n(n - 1)/2 and time complexity = n(n - 1)/2 * O(1) = O(n^2). We use constant extra space, so space complexity = O(1).
Using extra memory and a binary search
Solution idea and steps
Here are some critical observations from the previous approach.
Observation 1: We are traversing the array linearly until the end to find the first greater element X[j] which is at maximum distance. So if we think from another perspective, for every X[i], we need to find the first greater element X[j] (j > i) from the right end and keep updating the max difference.
Observation 3: There can be several values that may have the same first greater element from the right side. For example, let's take an array [4, 9, 2, 12, 3, 8, 7, 1]. For 4, 2 and 3: Here, 7 is the first greater element from the right end. Here critical questions are: Can we find an efficient way to keep track of the greater element moving from end to start? Can we pre-process input to find such an element efficiently? Think!
Suppose we use an extra array maxFromEnd[ ], where maxFromEnd[i] stores the max element from the right end to index i. So this array will be in decreasing order. For example, maxFromEnd[] of array [4, 9, 2, 12, 3, 8, 7, 1] will be [12, 12, 12, 12, 8, 8, 7, 1].
Now for each X[i], we can easily find the first greater element X[j] from the right end using maxFromEnd[]. One idea is to search linearly on maxFromEnd[] from index i to the right side for finding the farthest point j, where X[i] <= maxFromEnd[j].
This will not help to improve time complexity because in the worst case, we need to traverse maxFromEnd[] till the end. Can we think to optimize this? Here maxFromEnd[] is sorted in decreasing order. So rather than linear search, we can apply binary search to find the index of rightmost greater element.
The overall idea would be:
- Using a single loop, we can store values in maxFromEnd[ ]. For every index i, we store the max element from the right end to index i in maxFromEnd[i].
- Now we run another loop to access each element X[i] and apply binary search on maxFromEnd[] to find the first greater element X[j] from the right end.
- We find the maximum difference of the indices (j, i) and track the overall max difference in a variable.
Solution code C++
int maxIndexDiff(int X[], int n)
{
int maxFromEnd[n + 1];
for (int i = 0; i <= n; i = i + 1)
maxFromEnd[i] = INT_MIN;
for (int i = n - 1; i >= 0; i = i - 1)
maxFromEnd[i] = max(X[i], maxFromEnd[i + 1]);
int maxDiff = -1;
for (int i = 0; i < n; i = i + 1)
{
int l = i + 1;
int r = n - 1;
int farthestIndex = i;
// Applying binary search to find the farthest index
// such that X[i] < X[farthestIndex]
while (l <= r)
{
int mid = l + (r - l) / 2;
if (X[i] <= maxFromEnd[mid])
{
// We store mid as the current answer and look
// further larger index to the right side
farthestIndex = max(farthestIndex, mid);
l = mid + 1;
}
else
r = mid - 1;
}
maxDiff = max(maxDiff, farthestIndex - i);
}
return maxDiff;
}Note: This code will return 0 when input values are sorted in decreasing order. How can we modify the above code to produce the correct output, i.e. -1? Think!
Solution code Python
def maxIndexDiff(X):
n = len(X)
maxFromEnd = [float('-inf')] * (n + 1)
for i in range(n - 1, -1, -1):
maxFromEnd[i] = max(X[i], maxFromEnd[i + 1])
maxDiff = -1
for i in range(n):
l = i + 1
r = n - 1
farthestIndex = i
while l <= r:
mid = l + (r - l) // 2
if X[i] <= maxFromEnd[mid]:
farthestIndex = max(farthestIndex, mid)
l = mid + 1
else:
r = mid - 1
maxDiff = max(maxDiff, farthestIndex - i)
return maxDiffTime and space complexity analysis
Time complexity = Time complexity of storing maxFromEnd[] + Time complexity of searching the farthest index for n elements = O(n) + n * O(logn) = O(n) + O(nlogn). Space complexity = O(n) for using extra space for maxFromEnd[].
Using sorting: Sorting (element, index) pairs in increasing order
Solution idea and steps
Another idea is to sort the array element by maintaining the order of its indexes. We do this by creating the (element, index) pairs for every element and sorting pairs in increasing order of their first value. One idea is simple: After sorting the(element, index) array, the problem will still be the same. Think!
Now we traverse the sorted array from the right and keep track of the farthest index found so far (farthestIndex) and the maximum difference found so far (maxDiff).
If currIndex > farthestIndex, we update the farthestIndex with the currIndex. Otherwise, we have found a pair for which X[currIndex] < X[farthestIndex] and currIndex < farthestIndex (Because the array is sorted and we are traversing from the right end). So we update the max difference i.e. maxDiff = max (maxDiff, farthestIndex - currIndex).
Solution code C++
int maxIndexDiff(int X[], int n)
{
vector<pair<int, int>> pairs;
for (int i = 0; i < n; i = i + 1)
pairs.emplace_back(X[i], i);
sort(pairs.begin(), pairs.end());
int maxDiff = -1;
int farthestIndex = INT_MIN;
for (int i = n - 1; i >= 0; i = i - 1)
{
int currIndex = pairs[i].second;
if (currIndex > farthestIndex)
farthestIndex = currIndex;
else
maxDiff = max(maxDiff, farthestIndex - currIndex);
}
return maxDiff;
}Solution code Python
def maxIndexDiff(X):
pairs = []
for i in range(len(X)):
pairs.append((X[i], i))
pairs.sort()
maxDiff = -1
farthestIndex = float('-inf')
for i in range(len(X) - 1, -1, -1):
currIndex = pairs[i][1]
if currIndex > farthestIndex:
farthestIndex = currIndex
else:
maxDiff = max(maxDiff, farthestIndex - currIndex)
return maxDiffTime and space complexity analysis
Time complexity = Time complexity of storing pairs in extra memory + Time complexity of sorting (element, index) pairs + Time complexity of finding the max difference using a single loop = O(n) + O(nlogn) + O(n) = O(nlogn).
Space complexity = O(n), for using extra space to store (element, index) pairs.
Efficient approach using extra memory and two-pointers
Solution idea and steps
Observation 1: For an element X[i], if there is an element smaller than X[i] on the left side of X[i], we do not need to consider X[i] for the left index.
Observation 2: Similarly for an element X[j], if there is a larger element on the right side of X[j], then we do not need to consider X[j] for the right index.
So the idea behind this approach is to:
- We build two arrays, LeftMin[] and RightMax[], such that LeftMin[i] holds the smallest element on the left side of i (inclusive), and RightMax[j] holds the largest element on the right side of j (inclusive) in the array.
- Now we traverse both of these arrays from left to right. While traversing LeftMin[] and RightMax[], if (LeftMin[i] < RightMax[j]), we update the max difference and move ahead in RightMax[j] to look for a higher j - i value.
- Otherwise, we move ahead LeftMin[] to look for smaller values because all elements on the left of LeftMin[i] are greater than or equal to LeftMin[i].
Solution code C++
int maxIndexDiff(int X[], int n)
{
int LeftMin[n], RightMax[n];
LeftMin[0] = X[0];
for (int i = 1; i < n; i = i + 1)
LeftMin[i] = min(X[i], LeftMin[i - 1]);
RightMax[n - 1] = X[n - 1];
for (int j = n - 2; j >= 0; j = j - 1)
RightMax[j] = max(X[j], RightMax[j + 1]);
int i = 0, j = 0, maxDiff = -1;
while (j < n && i < n)
{
if (LeftMin[i] <= RightMax[j])
{
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
//When array is sorted in decreasing order
if(maxDiff == 0)
return -1;
else
return maxDiff;
}Solution code Python
def maxIndexDiff(X, n):
LeftMin = [0] * n
RightMax = [0] * n
LeftMin[0] = X[0]
for i in range(1, n):
LeftMin[i] = min(X[i], LeftMin[i - 1])
RightMax[n - 1] = X[n - 1]
for j in range(n - 2, -1, -1):
RightMax[j] = max(X[j], RightMax[j + 1])
i = 0
j = 0
maxDiff = -1
while j < n and i < n:
if LeftMin[i] <= RightMax[j]:
maxDiff = max(maxDiff, j - i)
j = j + 1
else:
i = i + 1
# When array is sorted in decreasing order
if maxDiff == 0:
return -1
else:
return maxDiffTime and space complexity analysis
The time complexity for the above algorithm is the time required to traverse the array i.e., O(n). The extra space required is proportional to the size of the array i.e. O(n).
Critical ideas to think!
- How do we modify the above code when there are repeated elements in the array?
- Can we solve this problem in a single scan by just creating the rightMax[] array?
- What would be the worst and best scenario of the above approaches?
- How can we modify the above approaches when we need to also return one of the pairs with a maximum difference?
- Can we solve this problem using some other approaches?
Suggested coding questions to practice
- Trapping rain-water
- Find the equilibrium index
- Find product except self
- Remove duplicates from sorted array
- Triplet in zero-sum
Enjoy learning, Enjoy coding!