Find the maximum j – i such that A[j] > A[i]

Difficulty: Medium, Asked-in: Amazon, 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 j  -  i such that j > i and X[j] > X[i].

Examples

Input: X[] = [31, 5, 7, 0, -1, 77, 27, 30, -2], Output: 6 (j = 7, i = 1)

Input: X[] = [1, 2, 3, 4, 5, 6], Output: 5 (j = 5, i = 0)

Input: X[] = [7, 6, 5, 4, 3, 2], Output: -1

Discussed solution approaches

  • A brute force approach  using nested loops 
  •  Using extra memory and a binary search
  • Using sorting: sorting (element, index) pairs in increasing order
  • An efficient approach  using extra memory and two-pointers

A brute force approach  using nested loops 

Solution idea

A straightforward method would be to explore every unique pair of elements (X[i], X[j]) using the nested loops. For each j > i, if we find some element X[j] > X[i], then we update the max difference i.e. if(X[j] > X[i]), maxDiff = max(maxDiff, j - i).

Here we pick the first element X[i] using the outer loop (i = 0 to n -2) and second element X[j] using the inner loop (j = i + 1 to n - 1). Note: This loop structure ensures that the value of j is always greater than i.

Solution Pseudocode

int maxIndexDiff(int X[], int n)
{
    int maxDiff = -1
    for(int i = 0; i < n - 1; i = i + 1)
    {
        for(int j = i + 1; i < n; j = j + 1)
        {
            if(X[j] > X[i])
                maxDiff = max(maxDiff, j - i)
        }
    }
    return maxDiff
}

Time and space complexity analysis

  • We are exploring every possible pair of elements using the nested loop. So total number of pairs = nC2 = n(n-1)/2. So time complexity = O(n^2).
  • Space Complexity = O(1).

Using extra memory and a binary search

Solution Idea and steps

Here are some critical observations from the previous approach

  • For every element X[i], we are looking to find the first greatest element from the end of the array to the current index i. In other words, we are finding an element X[j] (> X[i]) on the right side of the array, which is at the max distance from the X[i].
  • We are also trying to find the first greatest element again and again for each element in the array. Let's take an array [4, 9, 2, 12, 3, 8, 7, 1]. For 4, 2, and 3: 7 is the first greater element from the right side of the array, and there is no need to find it again and again. Can we find a way to keep track of the greater element moving from the end to the start of the array? Think!
  • In the brute force approach, we traverse the array linearly until the end to find the first greater element X[j]. The critical question is: can we pre-process the input and find the first greater element efficiently? Let's think!

Suppose we are using the extra array temp[] of size n, where at any position temp[i], we store the value of the max element from the right end to index current index i. So this array will be in decreasing order. For array [4, 9, 2, 12, 3, 8, 7, 1], the temp array will be [12, 12, 12, 12, 8, 8, 7, 1].

Using the temp[] array, for each element X[i], we can easily find the first greater element X[j] from the end and calculate the max distance j - i. One idea would be to search linearly on temp[] from index i to the right side of the array and find the farthest point j, where X[i] <= temp[j]. But this would not improve the time complexity because we need to search in temp[] array till end using linear search? Can we think of optimizing this process?

Here temp[] array is sorted in decreasing order. So rather than using linear search, we can think to apply the idea of binary search to find the index of the rightmost greater element. The overall idea would be:

  • Use binary search for each of the elements in the array.
  • Find the maximum difference of the indices.
  • Track the overall max difference of the array.

Solution Pseudocode

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 maxIndex = i
        while (l <= r) 
        {
            int mid = (l + r) / 2
            if (X[i] <= MaxFromEnd[mid]) 
            {
                maxIndex = max(maxIndex, mid)
                l = mid + 1
            }
            else
                r = mid - 1
        }
        maxDiff = max(maxDiff, maxIndex - i)
    }
    return maxDiff
}

Time and space complexity analysis

  • Time complexity = Time complexity of storing MaxFromEnd[] array + Time complexity of searching the index of the rightmost greater element for n elements = O(n) + n * O(logn) = O(nlogn)
  • Space complexity = O(n) for using extra space for MaxFromEnd[] array.

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 sort pairs in increasing order of their first value. One idea is straightforward: after sorting the index array, the problem will still be the same. Think!

Now we traverse the index array from the right and keep track of the maximum difference found so far. If the current index is less than the maximum index found so far and their difference is maximum than max difference found so far, we update the maximum difference with the current index.

Solution Pseudocode

int maxIndexDiff(int X[], int n)
{
    vector<pair<int, int>> pairs
    for (int i = 0; i < n; i = i + 1) 
        pairs.push_back(X[i], i)
        
    sort(pairs.begin(), pairs.end())
    
    int maxDiff = -1
    int max_index_so_far = INT_MIN
    for (int i = n - 1; i >= 0; i = i - 1)
    {
        int currIndex = pairs[i].second
        if (currIndex > max_index_so_far) 
            max_index_so_far = currIndex
        else 
            maxDiff = max (maxDiff, max_index_so_far - currIndex)
    }
    return maxDiff
}

Time and space complexity analysis

  • Time complexity = Time complexity of storing pairs in extra memory + Time complexity of sorting element-index pair + 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.

An 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 left side of X[i], we do not need to consider X[i] for the left index.

Observation 2: Similarly, if there is a larger element on the right side of X[j], then we do not need to consider this X[j] for the right index.

So the idea behind this approach is to:

  • Build two arrays LeftMin[] and RightMax[] such that LeftMin[i] holds the smallest element on the left side of ‘i’ (inclusive) in the array, and RightMax[j] holds the greatest 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 PseudoCode

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 (j = n - 2; j >= 0; j = j - 1)
        RightMax[j] = max(X[j], RightMax[j + 1]);    
        
    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
    }
    return maxDiff
}

Time and space complexity analysis

Time Complexity: The time complexity for the above algorithm is the time required to traverse the array i.e., O(n). Space Complexity: 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?
  • Instead of using binary search for Can we further optimize the last approach? 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

Enjoy learning, Enjoy coding!

We welcome your comments

Subscribe Our Newsletter

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.