Distance Maximizing Problem

11 Dec 2011

Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].

This is a really really good interview question. I love this kind of questions.

It is simple and bears different solutions. Following a good practice, the simplistic solution should be laid down first.

We can just do a brute-force solution, iterating through every pair and get the maximum. That is O(n^2) in time.

In order to get a better solution, we need more insights.

Observation 1

It's all about random exploration, right?

Let's say we have:

a[0] a[1] a[2] a[3] ... a[n-1]

Since we want to find the maximum of j-1. It makes sens to start with 2 pointers at a[0] and a[n-1]. If a[0] < a[n-1], we get the solution immediately. If it is not, what do we do?

We got nothing.

I cannot come up with any observation. Oh god.

Ok, let's have a look at Leetcode.com.

Leetcode.com's super cool solution

Let's say we have:

10 5 9 4 3 1 6 8 2

If we have the solution already, 6 will never be a part of the answer. This is because it is always better to choose 1 rather than 6. (1 is more on the left and is lesser.)

Now it's obvious that the only possible starting points are 5, 4, 3, and 1.

This is a crucial observation. We can devise an O(n) solution from it. I'll leave it as an exercise for future Tanin.

Lesson Learned

One way to find useful observations is to consider all possible solutions and rule out some combinations.

Give it a kudos