# C++ Maximum Index Problem

Given an array A[] of positive integers. We will find the maximum of (j-i) such that i and j are the indexes of A[] and A[i] <= A[j], i<=j

For example

Input:

`N = 2A[] = {1, 20}`

Output:

`1`

Explanation:

A[0]<A[1] so (j-i) is 1-0 = 1.

Input:

`N = 10A[] = {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}`

Output:

`8`

Explanation:

In the given array A[0] < A[8]

satisfying the required condition(A[i] < A[j]) thus giving the maximum difference of j - i which is 8(8-0).

Approach 1

The approach is simple but inefficient. Run two loops. The outer loop will pick the element from the left and the inner loop will pick the element from the right.

Check if the element picked in the inner loop is greater than the element picked in the outer loop. Stop the inner loop and store the difference of (j-i).

Likewise, do the process for the entire array and update the maximum difference of (j-i).

Code (C++)

`#include <bits/stdc++.h>using namespace std;// Function to find the max differenceint maxIndexDiff(int arr[], int n){          int maxDiff = -1; // Let current max diff is -1          int i, j; // Initialize two variables          for (i = 0; i < n; ++i) { // outer loop                   for (j = n - 1; j > i; --j) { // inner loop                             if (arr[j] > arr[i] && maxDiff < (j - i)) // if element is greater and current maxdiff is less than the new one update the maxdiff                                      maxDiff = j - i;                   }          }          return maxDiff; // return the max difference}int main(){          int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };          int n = sizeof(arr) / sizeof(arr[0]); // Find the size of the array          int maxDiff = maxIndexDiff(arr, n); // Call the function to calculate maximum difference          cout << "Maximum difference is " << maxDiff;          return 0;}`

Output

`Maximum difference is 8`

Code (C language)

`#include <stdio.h>// Function to find the max differenceint maxIndexDiff(int arr[], int n){          int maxDiff = -1; // Let current max diff is -1          int i, j; // Initialize two variables          for (i = 0; i < n; ++i) { // outer loop                   for (j = n - 1; j > i; --j) { // inner loop                             if (arr[j] > arr[i] && maxDiff < (j - i)) // if element is greater and current maxdiff is less than the new one update the maxdiff                                      maxDiff = j - i;                   }          }          return maxDiff; // return the max difference}int main(){          int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };          int n = sizeof(arr) / sizeof(arr[0]); // Find the size of the array          int maxDiff = maxIndexDiff(arr, n); // Call the function to calculate maximum difference          printf("Maximum difference is %d", maxDiff);          return 0;}`

Output

`Maximum difference is 8`

Time complexity - O(n*n)

Approach 2

After analyzing the brute force approach, it is observed that for every element in the outer loop, we find the maximum in the inner loop. This means for every window we find a maximum element.

For example, in A =  [1, 5, 12, 4, 9]

9 is greater than 1, 5, 4. Now to avoid finding the maximum again and again we can keep the track of the maximum number moving from the end to start of the array.

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.

Code

`#include <bits/stdc++.h>using namespace std;int main(){          vector<long long int> v{ 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 }; // Take a vector          int n = v.size(); // Find the size of the vector          vector<long long int> maxFromEnd(n + 1, INT_MIN); // A vector to keep the max from end          // create an array maxfromEnd          for (int i = v.size() - 1; i >= 0; i--) {                   maxFromEnd[i] = max(maxFromEnd[i + 1], v[i]);          }          int result = 0; //store max difference as result          // use  binary search here          for (int i = 0; i < v.size(); i++) {// set low and high pointer                   int low = i + 1, high = v.size() - 1, ans = i;                   while (low <= high) {                             int mid = (low + high) / 2; // find the mid element                             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); // calculate current max diff                                      low = mid + 1;                             }                             else {                                      high = mid - 1;                             }                   }                   // keeping a track of the                   // maximum difference in indices                   result = max(result, ans - i);          }          cout <<"Maximum difference is " << result << endl;}`

Output

`Maximum difference is 8`

Time complexity - O(n * logn)

Approach 3

By taking special care of the duplicates the problem can be solved in less than quadratic complexity.

• To handle the duplicates, traverse the array and store each element index in a list.
• Sort the array and then traverse it by keeping track of the maximum difference of i and j.
• For j, the last index of the list will be taken and for i keep the first index from the list.
• Update the maximum index and traverse the array upto last.

Code

`#include <bits/stdc++.h>using namespace std;int maxIndexDiff(vector<int>& arr, int n) // Function to find max difference{          unordered_map<int, vector<int> > hashmap; // create unordered map// Loop till the array end          for (int i = 0; i < n; i++) {                   hashmap[arr[i]].push_back(i); // Insert the index of a particular element          }          // Sort arr          sort(arr.begin(), arr.end());          int maxDiff = INT_MIN; // Let max difference is mimimum in the begining          int temp = n; // take the size of array in temp          // Iterate in the array          for (int i = 0; i < n; i++) {                   if (temp > hashmap[arr[i]][0]) { // Compare the index to avoid overflow                             temp = hashmap[arr[i]][0];                   }                   maxDiff = max( // find max difference                             maxDiff,                             hashmap[arr[i]][hashmap[arr[i]].size() - 1]                                      - temp);          }          return maxDiff; // return max difference}int main(){          int n = 9; // size of vector          vector<int> arr{ 34, 8, 10, 3, 2, 80, 30, 33, 1 }; // vector elements          int ans = maxIndexDiff(arr, n); // call the function          cout << "The maxIndexDiff is : " << ans << endl; // print the result          return 1;}`

Output

`The maxIndexDiff is: 6`

Time complexity

O(nlogn)

Space complexity

O(1)