Objective: Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].
Example :

int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 };
Output: Max(j-i) where j>i and A[j]>A[i] is : 7
Approach:

Create 2 Auxilary Arrays say Lmin[] and Rmax[] of the same size as main array
Put Lmin[0]=0 and Rmax[Rmax.length-1] =Rmax.length-1
Traverse the main array and fill the Lmin array with the index position which has the minimum value so far
Traverse the main array backwords and fill the Rmax array with the index position which has the maximun value so far
Initialize distance_so_far = 0
Navigate through the main array and if (Lmin[i]<Rmax[i])
Then check if (Rmax[i]-Lmin[i])>distance_so_far then distance_so_far = Rmax[i]-Lmin[i]
Return distance_so_far
Complete Code: Run This Code

Output:

Max(j-i) where j>i and A[j]>A[i] is : 7
__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Like this: Like Loading...