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 = 2
A[] = {1, 20}
Output:
1
Explanation:
A[0]<A[1] so (j-i) is 1-0 = 1.
Input:
N = 10
A[] = {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 difference
int 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 difference
int 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.
- Traverse the array from the end and keep a track of the maximum number to the right of the current index including self.
- Now we have a monotonous decreasing array, and we know we can use binary search to find the index of the rightmost greater element
- 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)