**Difficulty:** Medium, **Asked-in:** Amazon, Google, Adobe, Hike

**Key takeaway:** An excellent problem to learn problem-solving using sorting, extra memory, and two-pointers approaches.

Given an unsorted array X[] of distinct elements, write a program to find the maximum difference between a pair of indices j and i such that j > i and X[j] > X[i]. Assume that all values in the input are distinct. **Note:** There can be several such pairs of indices for which the difference will be maximum. We just need to return the max difference between j - i.

**Example 1**

Input: X[] = [40, 20, 70, 10, -20, 80, 30, -10], Output = 5

Explanation: There are two such pairs with maximum index difference: (40, 80) and (20, 30). Index difference between (40, 80) = 5 - 0 = 5, and index difference between (20, 30) = 6 - 1 = 5.

**Example 2**

Input: X[] = [1, 2, 3, 4, 5, 6], Output = 5 (j = 5, i = 0)

Explanation: Array is sorted in increasing order. So the max difference between the first and last index will be the maximum of j - i.

**Example 3**

Input: X[] = [7, 6, 5, 4, 3, 2], Output = -1

Explanation: Array is sorted in decreasing order. So no such max difference exists in the array.

- Brute force approach using nested loops
- Using extra memory and binary search
- Using sorting: Sorting (element, index) pairs in increasing order
- Efficient approach using extra memory and two-pointers

A basic idea would be to explore every pair of indices (j > i) using nested loops. If (X[j] > X[i]), we update the max difference i.e. if(X[j] > X[i]), maxDiff = max (maxDiff, j - i).

Here we pick the first index using the outer loop (i = 0 to n - 2) and the second index using the inner loop (j = i + 1 to n - 1). This loop structure ensures that the value of j is always greater than i.

```
int maxIndexDiff(int X[], int n)
{
int maxDiff = -1
for(int i = 0; i < n - 1; i = i + 1)
{
for(int j = i + 1; i < n; j = j + 1)
{
if(X[j] > X[i])
maxDiff = max(maxDiff, j - i)
}
}
return maxDiff
}
```

We explore every possible pair of indices using a nested loop and perform constant operations at each iteration. Total number of pairs = nC2 = n(n - 1)/2 and time complexity = n(n - 1)/2 * O(1) = O(n^2). We use constant extra space, so space complexity = O(1).

Here are some critical observations from the previous approach.

**Observation 1:** We are traversing the array linearly until the end to find the first greater element X[j] which is at maximum distance. So if we think from another perspective, for every X[i], we need to find the first greater element X[j] (j > i) from the right end and keep updating the max difference.

**Observation 3:** There can be several values that may have the same first greater element from the right side. For example, let's take an array [4, 9, 2, 12, 3, 8, 7, 1]. For 4, 2 and 3: Here, 7 is the first greater element from the right end. Here critical questions are: Can we find an efficient way to keep track of the greater element moving from end to start? Can we pre-process input to find such an element efficiently? Think!

Suppose we use an extra array **maxFromEnd[ ]**, where maxFromEnd[i] stores the max element from the right end to index i. So this array will be in decreasing order. For example, maxFromEnd[] of array [4, 9, 2, 12, 3, 8, 7, 1] will be [12, 12, 12, 12, 8, 8, 7, 1].

Now for each X[i], we can easily find the first greater element X[j] from the right end using maxFromEnd[]. One idea is to search linearly on maxFromEnd[] from index i to the right side for finding the farthest point j, where X[i] <= maxFromEnd[j].

This will not help to improve time complexity because in the worst case, we need to traverse maxFromEnd[] till the end. Can we think to optimize this? Here maxFromEnd[] is sorted in decreasing order. So rather than linear search, we can apply binary search to find the index of rightmost greater element.

The overall idea would be:

- Using a single loop, we can store values in maxFromEnd[ ]. For every index i, we store the max element from the right end to index i in maxFromEnd[i].
- Now we run another loop to access each element X[i] and apply binary search on maxFromEnd[] to find the first greater element X[j] from the right end.
- We find the maximum difference of the indices (j, i) and track the overall max difference in a variable.

```
int maxIndexDiff(int X[], int n)
{
int maxFromEnd[n + 1]
for(int i = 0; i <= n; i = i + 1)
maxFromEnd[i] = INT_MIN
for (int i = n - 1; i >=0; i = i - 1)
maxFromEnd[i] = max(X[i], maxFromEnd[i + 1])
int maxDiff = -1
for (int i = 0; i < n; i = i + 1)
{
int l = i + 1
int r = n - 1
int farthestIndex = i
// Applying bianry search to find the farthest index
// Such that X[i] < X[farthestIndex]
while (l <= r)
{
int mid = l + (r - l) / 2
if (X[i] <= maxFromEnd[mid])
{
// We store mid as the current answer and look
// further larger index to the right side
farthestIndex = max(farthestIndex, mid)
l = mid + 1
}
else
r = mid - 1
}
maxDiff = max(maxDiff, farthestIndex - i)
}
return maxDiff
}
```

Time complexity = Time complexity of storing maxFromEnd[] + Time complexity of searching the farthest index for n elements = O(n) + n * O(logn) = O(n) + O(nlogn). Space complexity = O(n) for using extra space for maxFromEnd[].

Another idea is to sort the array element by maintaining the order of its indexes. We do this by creating the (element, index) pairs for every element and sorting pairs in increasing order of their first value. One idea is simple: After sorting the(element, index) array, the problem will still be the same. Think!

Now we traverse the sorted array from the right and keep track of the farthest index found so far (farthestIndex) and the maximum difference found so far (maxDiff).

If currIndex > farthestIndex, we update the farthestIndex with the currIndex. Otherwise, we have found a pair for which X[currIndex] < X[farthestIndex] and currIndex < farthestIndex (Because the array is sorted and we are traversing from the right end). So we update the max difference i.e. maxDiff = max (maxDiff, farthestIndex - currIndex).

```
int maxIndexDiff(int X[], int n)
{
vector<pair<int, int>> pairs
for (int i = 0; i < n; i = i + 1)
pairs.push_back(X[i], i)
sort(pairs.begin(), pairs.end())
int maxDiff = -1
int farthestIndex = INT_MIN
for (int i = n - 1; i >= 0; i = i - 1)
{
int currIndex = pairs[i].second
if (currIndex > farthestIndex)
farthestIndex = currIndex
else
maxDiff = max (maxDiff, farthestIndex - currIndex)
}
return maxDiff
}
```

Time complexity = Time complexity of storing pairs in extra memory + Time complexity of sorting (element, index) pairs + Time complexity of finding the max difference using a single loop = O(n) + O(nlogn) + O(n) = O(nlogn).

Space complexity = O(n), for using extra space to store (element, index) pairs.

**Observation 1:** For an element X[i], if there is an element smaller than X[i] on the left side of X[i], we do not need to consider X[i] for the left index.

**Observation 2:** Similarly for an element X[j], if there is a larger element on the right side of X[j], then we do not need to consider X[j] for the right index.

So the idea behind this approach is to:

- We build two arrays,
**LeftMin[]**and**RightMax[]**, such that LeftMin[i] holds the smallest element on the left side of i (inclusive), and RightMax[j] holds the largest element on the right side of j (inclusive) in the array. - Now we traverse both of these arrays from left to right. While traversing LeftMin[] and RightMax[], if (LeftMin[i] < RightMax[j]), we update the max difference and move ahead in RightMax[j] to look for a higher j - i value.
- Otherwise, we move ahead LeftMin[] to look for smaller values because all elements on the left of LeftMin[i] are greater than or equal to LeftMin[i].

```
int maxIndexDiff(int X[], int n)
{
int LeftMin[n], RightMax[n]
LeftMin[0] = X[0]
for (int i = 1; i < n; i = i + 1)
LeftMin[i] = min(X[i], LeftMin[i - 1])
RightMax[n - 1] = X[n - 1]
for (j = n - 2; j >= 0; j = j - 1)
RightMax[j] = max(X[j], RightMax[j + 1]);
i = 0, j = 0, maxDiff = -1
while (j < n && i < n)
{
if (LeftMin[i] <= RightMax[j])
{
maxDiff = max(maxDiff, j - i)
j = j + 1
}
else
i = i + 1
}
return maxDiff
}
```

The time complexity for the above algorithm is the time required to traverse the array i.e., O(n). The extra space required is proportional to the size of the array i.e. O(n).

- How do we modify the above code when there are repeated elements in the array?
- Can we solve this problem in a single scan by just creating the rightMax[] array?
- What would be the worst and best scenario of the above approaches?
- How can we modify the above approaches when we need to also return one of the pairs with a maximum difference?
- Can we solve this problem using some other approaches?

- Trapping rain-water
- Find the equilibrium index
- Find product except self
- Move zeroes to an end
- Container With Most Water
- Remove duplicates from sorted array
- Whether an array is a subset of another array
- Find the intersection of two arrays
- Triplet in zero-sum

**Enjoy learning, Enjoy coding!**

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.