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

Software Development
#1

Hello Everyone,

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

Examples :

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1

Method 1 (Simple)
Run two loops. In the outer loop, pick elements one by one from the left. In the inner loop, compare the picked element with the elements starting from the right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.

// C program for the above approach

#include <stdio.h>

/* For a given array arr[],

returns the maximum j – i such

that arr[j] > arr[i] */

int maxIndexDiff( int arr[], int n)

{

int maxDiff = -1;

int i, j;

for (i = 0; i < n; ++i) {

for (j = n - 1; j > i; --j) {

if (arr[j] > arr[i] && maxDiff < (j - i))

maxDiff = j - i;

}

}

return maxDiff;

}

int main()

{

int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };

int n = sizeof (arr) / sizeof (arr[0]);

int maxDiff = maxIndexDiff(arr, n);

printf ( "\n %d" , maxDiff);

getchar ();

return 0;

}

Output

8

Time Complexity: O(n^2)

Method 2 –
Improvising the Brute Force Algorithm and looking for BUD, i.e Bottlenecks, unnecessary and duplicated works. A quick observation actually shows that we have been looking to find the first greatest element traversing from the end of the array to the current index. We can see that we are trying to find the first greatest element again and again for each element in the array. Let’s say we have an array with us for example [1, 5, 12, 4, 9] now we know that 9 is the element that is greater than 1, 5, and 4 but why do we need to find that again and again. We can actually keep a track of the maximum number moving from the end to the start of the array. The approach will help us understand better and also this improvisation is great to come up with in an interview.

Approach :

  1. Traverse the array from the end and keep a track of the maximum number to the right of the current index including self
  2. Now we have a monotonous decreasing array, and we know we can use binary search to find the index of the rightmost greater element
  3. Now we will just use binary search for each of the elements in the array and store the maximum difference of the indices and that’s it we are done.

/* For a given array arr[],

calculates the maximum j – i

such that arr[j] > arr[i] */

#include <bits/stdc++.h>

using namespace std;

int main()

{

vector< long long int > v{

34, 8, 10, 3, 2, 80, 30, 33, 1

};

int n = v.size();

vector< long long int > maxFromEnd(n + 1, INT_MIN);

// create an array maxfromEnd

for ( int i = v.size() - 1; i >= 0; i--) {

maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]);

}

int result = 0;

for ( int i = 0; i < v.size(); i++) {

int low = i + 1, high = v.size() - 1, ans = i;

while (low <= high) {

int mid = (low + high) / 2;

if (v[i] <= maxFromEnd[mid]) {

// We store this as current answer and look

// for further larger number to the right

// side

ans = max(ans, mid);

low = mid + 1;

}

else {

high = mid - 1;

}

}

// keeping a track of the

// maximum difference in indices

result = max(result, ans - i);

}

cout << result << endl;

}

Output

6

Time complexity : O(N*log(N))
Space complexity: O(N)

Method 3 O(nLgn):
Use hashing and sorting to solve this problem in less than quadratic complexity after taking special care of the duplicates.
Approach :

  1. Traverse the array and store the index of each element in a list (to handle duplicates).
  2. Sort the array.
  3. Now traverse the array and keep track of the maximum difference of i and j.
  4. For j consider the last index from the list of possible index of the element and for i consider the first index from the list. (As the index were appended in ascending order).
  5. Keep updating the max difference till the end of the array.

// C++ implementation of

// the hashmap approach

#include <bits/stdc++.h>

using namespace std;

// Function to find maximum

// index difference

int maxIndexDiff(vector< int >& arr, int n)

{

// Initilaise unordered_map

unordered_map< int , vector< int > > hashmap;

// Iterate from 0 to n - 1

for ( int i = 0; i < n; i++) {

hashmap[arr[i]].push_back(i);

}

// Sort arr

sort(arr.begin(), arr.end());

int maxDiff = INT_MIN;

int temp = n;

// Iterate from 0 to n - 1

for ( int i = 0; i < n; i++) {

if (temp > hashmap[arr[i]][0]) {

temp = hashmap[arr[i]][0];

}

maxDiff = max(

maxDiff,

hashmap[arr[i]][hashmap[arr[i]].size() - 1]

- temp);

}

return maxDiff;

}

// Driver Code

int main()

{

int n = 9;

vector< int > arr{ 34, 8, 10, 3, 2, 80, 30, 33, 1 };

// Function Call

int ans = maxIndexDiff(arr, n);

cout << "The maxIndexDiff is : " << ans << endl;

return 1;

}

Output

The maxIndexDiff is : 6

Time complexity : O(N*log(N))