Return the Maximum absolute difference of values and indices

In this article we will be discussing one of the most asked coding interview question asked at Amazon.
The problem statement goes as follows:

Problem statement

Given an array A determine the maximum possible value of the following expression:
$f(i,j) =| A[i]-A[j] | +|i-j|$

Example

Input : A = {1, 3, -1} 
Output : 5
because the maximum value obtainable is:
=> f(1,2) = |3 - (-1)| + |1-2| = 5

Input : A={3, -2, 5, -4}
Output : 10
=> f(1, 4) = f(4, 1) = |3 - (-4)| + |1 - 4| = 10
Note that in this case we can also obtain 10 from
=> f(3, 4) = f(4, 3) = |5 - (-4)| + |3 - 4| = 10

Solution Approach

We will start by noticing that writing a brute force solution is quite an easy task.
We simply need to loop over all the possible pairs and calculate the maximum value of $f(i,j)$ .
This approach has a complexity of $O(n^2)$ as we need to check all possible pairs of indexes.

We can do better than this. We are seeking a linear time solution.

Let's start by noticing that:

$f(i,j) = f(j,i)$
$|A[i] -A[j]| + |i-j| = |A[j] -A[i]| + |j-i|$

For this reason there is no need to consider the case where $i < j$ and we can remove the absolute value from that part of the equation. So $f$ now is:

$f(i,j) = |A[i] - A[j]| + i-j$

The other interesting fact we can notice is that we can rewrite the expression to remove all absolute values alltogether is we make some assumption on the possible value of $A[i]$ and $A[j]$.
For instance if we assume $A[i] \geq A[j]$ then:

$f(i,j) = A[i] - A[j] + i-j$

and if we assume $A[j] \geq A[i]$ then:

$f(i,j) = -A[i] + A[j] + i-j$

What we really have to to is to figure out how we can maximise the quations 1 and 2.
Let's rewrite them a bit:

$f(i,j) = A[i] - A[j] + i-j = (A[i] +i) - (A[j] +j)$
$f(i,j) = -A[i] + A[j] + i-j = (-A[i]+ i) + (A[j] - j) = (A[j] - j) - (A[i]-i)$

We can clearly see that in order to maximixe 1 we need to find the highest value for $(A[i] +i) $ and pair it up with the smallest value for $(A[j] +j)$.
Simmetrically for equation 2 we need to maximixe $(A[j] - j)$ and to mimimize $(A[i]-i)$.

Final solution approach

So the problem boils down to basically finding both the mimimum and maximum values for the expressions:

$(A[i]+i)$
$(A[i]-i)$

This task can be easily accomplished in linear time as finding max and min in an array should be pretty straightforward.

C++ code

The idea above can be coded as follows:

int max_abs(const vector<int>&amp;A)
{
    //min_m = min(A[i]-i)
    //max_m = max(A[i]-i)
    //max_p = max(A[i]+i)
    //min_p = min(A[i]+i)
    int min_m, min_p;
    int max_m, max_p;

    min_m = min_p = numeric_limits<int>::max();
    max_m = max_p = numeric_limits<int>::min();
    for(int i = 0; i < A.size() ; i++)
    {
        min_m = min(min_m, A[i]-i);
        max_m = max(max_m, A[i]-i);

        min_p = min(min_p, A[i]+i);
        max_p = max(max_p, A[i]+i);
    }
    return max(max_m - min_m , max_p - min_p);
}

The complexity of the code above is linear in the size of A.
You can try the above code online on Wandbox.

Conclusions

In this article we discussed a common coding interview question asked by many tech companies. The takeaways from this exercises are:

When a formula appears in the problem statement, always try to rewrite it and deduce as much info as you can from making assumptions on the terms appearing in it.

If you like this article check the previous article of the series ( Sort an array of size N made of numbers from 0 to K ).

The most asked coding interview - #4