Given an array V, we need to find two indices (i,j) such that V[j] > V[i] and (j - i) is maximum

Question

Given an array V, we need to find two indices (i,j) such that V[j] > V[i] and (j - i) is maximum.

The brute force approach is pretty straight forward wherein for each value at index i (ranging from 1 to n), we compare value at index j (ranging from i+1 to n). We keep track of maximum (j-i) so far to find the final answer.

This approach has the time complexity of O(n^2). Does anybody have any suggestions on improving the time complexity?

Answer 1

Here's an approach that will solve the problem in linear time.

1. Compute the stack S of increasing positions i such that min A[1..i-1] > i with a simple forwards scan over the array.
2. Iterate over the list backwards.
3. While the current element is greater than the value given by the top of the stack S: check if we have a new record and pop the top of the stack.

A quick implementation in python:

def notsurewhattonamethis(A):
    assert(A)
    S = [0]
    for i,v in enumerate(A):
        if v<A[S[-1]]:
            S.append(i)
    best = (-1,-1)
    for i,v in reversed(list(enumerate(A))):
        while v>A[S[-1]]:
            j = S.pop()
            d = i - j
            if d > best[1]-best[0]:
                best = (j,i)
            if not S: return best
    return best