Calculate the Max Distance in an Array

Teiva Harsanyi

Published in

solvingalgo

4 min readSep 28, 2018

Problem

Max distance: InterviewBit

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].Example:Input A: [3, 5, 4, 2]
Output: 2 for the pair (3, 4)

Category: Arrays

Solving Process

Brute Force

One brute force solution consists in iterating over each pair of the array and finding the maximum of j - i. This solution is O(n²).

Let’s try to find a better solution.

Recursion

A common technique with array problems is to have two pointers.

As we need to find the maximum of j - i, let’s try to initialize the pointers at the start and the end of the array.

A: 3  5  4  2
   i        j

If we already get A[i] <= A[j], we don’t even have to iterate and we can return j - i which is equals to size(A) - 1.

Yet, in our example, this is not the case.

How to move i and/or j?

A solution would be to try both cases by:

Moving i to the right
Moving j to the left

And then return the maximum of both sub solutions.

In Java:

Please note in this possible implementation we do not use i or j. Instead, we use List.subList(fromIndex, toIndex) which returns a view of the list (cc Val Deleplace ;).

Despite being elegant and concise, this code is not really efficient. The space complexity is O(n) due to recursion calls and the time complexity is O(2^n) as for each call we need to do two sub calls.

We could try to optimize it using dynamic programming techniques but let’s move on.

What if we try to figure out whether another solution exists using those two pointers:

A: 3  5  4  2
   i        j

In this example we should ask ourselves, is there any way to guess whether it’s i or j that should be moved?

In the previous example, we know the solution is (3, 4) so we should move j to the left. As A[i] equals 3 and A[j] equals 2, does it mean we have to move each time the pointer with the smallest value?

To validate/invalidate this theory, let’s take another example:

A: 4  3  1  2
Output: 1 for the pair (1, 2)

If we apply our theory:

A: 4  3  1  2
   i        j // Initial situation   4  3  1  2
   i     j    // We move j as A[j] < A[i]

In this example, our theory is not going to work as j should be at position 3 at the end of the algorithm.

This is the end of the road for the two-pointers technique. Let’s try something different.

Sorted Array

If you are familiar with the Solving Algo publications, I already mention another strategy: the inputs simplification. With arrays, the most common simplification is sorting.

What if the input array was sorted? As we need to calculate a distance based on the indexes, we must keep track of the original indexes. Not just blindly sort the array.

One possible solution in Java to deal with that is to implement our own helper class:

Helper stores a value and an index variable and implements a sorting strategy based on the value.

We can iterate over A and construct a collection of Helper. Once sorted, we would have something like that:

A: 3  5  4  2Helpers: (2, 3), (3, 0), (4, 2), (5, 1)

If we represent the Helper collection in a different way:

Values:  2  3  4  5
Indexes: 3  0  2  1

Let’s come back to the initial problem. We need to find max(j - i) with the constraint A[i] <= A[j].

As the collection is sorted by value we know that if we take one random element, every element on its right respects the constraint A[i] <= A[j].

As we must find max(j - i), the solution is to build a rightMax array containing the maximum index starting from the right of the Helper collection.

In pseudo-code:

int[] rightMax = new int[size]
int maxValue = IntegerMinValuefor (i = size - 1; i >= 0; i--) {
  maxValue = max(maxValue, helper[i].index)
  rightMax[i] = maxValue
}

With the previous example, rightMax would be equals to [3, 2, 2, 1].

Then, we iterate over the Helper collection and rightMax to return the maximum difference of rightMax[i] - helpers[i].index.

As we need to find max(j - i) it’s crucial to iterate until the end and not just return the first pair validating A[i] <= A[j].

A possible implementation in Java:

What about the complexity:

Space: we must construct two collections (helpers and rightMax) with the same size than A so it’s an O(n) solution
Time: the most significant part of the overall algorithm is the sorting operation so it’s an O(n log(n)) solution