Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

Optimized Approach

We want to find two optimal arr[] indexes, left(i) and right(j). If there is an element less than arr[i] on the left side of arr[i], we will not need to consider arr[i] for the left index. We have a similar situation on the right side. So we create two arrays, leftMin[] and rightMax[], with leftMin[i] holding the lowest member on the left side of arr[i], and rightMax[j] holding the maximum element on the right side. Both of these arrays are traversed from left to right. If we notice that leftMin[i] is bigger than rightMax[j] when traversing leftMin[] and rightMax[], we must move ahead in leftMin[]. Otherwise, we must move ahead in rightMax[j] to find a higher j – I value.

Algorithm

1. Declare two arrays leftMin[] and rightMax[].

2. Create leftMin[] so that leftMin[i] holds the smallest value from (arr[0], arr[1], ... arr[i]).

3. Create rightMax[] such that it holds the maximum value from (arr[j], arr[j+1],...arr[n-1]). 

4. From left to right, traverse both arrays to get the optimal j - I and save it in a variable. If leftMin[i] = rightMax[j], we update the variable with the maximum j-i value.

5. Return the maximum value.

Implementation

#include <bits/stdc++.h>
using namespace std;
int differenceCalc(int nums[], int n)
{
    int diffMax;
    int i, j;
    int *leftMin = new int[(sizeof(int) * n)];
    int *rightMax = new int[(sizeof(int) * n)];
 
    /* Construct leftMin[] so that
    leftMin[i] has minimum value till i-th index*/
 
    leftMin[0] = nums[0];
 
    for (i = 1; i < n; ++i)
        leftMin[i] = min(nums[i], leftMin[i - 1]);
 
    /* Construct rightMax[] such that
    rightMax[j] has the maximum value from j-th index */
 
    rightMax[n - 1] = nums[n - 1];
 
    for (j = n - 2; j >= 0; --j)
        rightMax[j] = max(nums[j], rightMax[j + 1]);
 
    /* Traverse both arrays from left to right
    to find the maximum value of j - i where arr[j] >= arr[i].*/
 
    i = 0, j = 0, diffMax = -1;
 
    while (j < n && i < n)
    {
        if (leftMin[i] <= rightMax[j])
        {
            diffMax = max(diffMax, j - i);
            j = j + 1;
        }
        else
            i = i + 1;
    }
 
    return diffMax;
}
// Driver Code
 
int main()
{
    int nums[] = {7, 1, 3, 6, 2, 4, 9};
 
    int n = sizeof(nums) / sizeof(nums[0]);
 
    cout << "The array is: " << endl;
 
    for (size_t i = 0; i < n; i++)
    {
        cout << nums[i] << " ";
    }
    cout << endl
         << "The maximum j-i value is: " << endl;
    int diffMax = differenceCalc(nums, n);
 
    cout << diffMax;
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Time Complexity

The Time complexity of the above approach is O(n) as there are only single loop traversals of the arrays in the entire solution.

Space Complexity

The Space complexity of the above approach is O(n) as it includes using two arrays for left minimum and right maximum values storage.

Frequently Asked Questions

What does the brute-force approach do in this problem?

We run two loops from left and right, respectively. We compare the two values on loops, and if we find an element such that arr[j] > arr[i], we update the maximum value of j-i maintained throughout the loop run.

What does sizeof() return?

It returns the variable's size. It may be used for any data type, including float and pointer variables.

Why would you use an array to hold a tree instead of tree nodes?

It takes less time to search. You may easily convert the array into a binary tree for a faster search time. The most significant benefit of using an array format for a tree is that you save memory by keeping fewer pointers.

Conclusion

This article extensively discussed the problem of finding the maximum value of j-i indexes of the array such that arr[j] > arr[i] in a given array and the time and space complexities of the solution presented.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Array Introduction, Array Interview Questions, Book Allocation Problem, 2-D Array, and 1-D Array.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problems, interview experiences, and interview bundle.

You should also consider our premium courses to offer your career advantage over others!

Please upvote our blogs if you find them useful and exciting!

Happy Coding!