Given an array, can I find in O(n) the longest range, whose endpoints are the greatest values in the range?

Question

For a given array of integers, find the maximum distance between 2 points (i and j) that have higher values ​​than any element between them.

Example:

 values: 0 10  8  9  6  7  4 10  0 index : 0  1  2  3  4  5  6  7  8  

for the values above the solution is i=1, j=7, but

• if the value of index 7 is 9 instead of 10 the solution is i=3, j=7
• if the value of index 7 is 7 instead of 10 the solution is i=5, j=7

I can't see a solution in O(n) ... anyone ?

Answer 1

A simple stack based solution. Iterate over the array left to right, with the stack holding elements (technically, indexes, but use values for comparisons) that are either:

1. The largest from the left (i.e. no larger or equal element between the start of the array and the element)
2. The largest since the previous element on the stack.

When processing the next element x, pop elements smaller than x as long as they are from the category 2. above, then push x on the stack. Obviously you need to keep the current max to be able to discern between category 2 and 1 in constant time.

The processing above is O(n) - each element can be pushed at most once and popped at most once. Having the final stack, just check neighboring pairs (on the stack) - one of the pairs is the solution. This too is O(n).

Here's a picture with what should stay on the stack (the fat rectangles) after the whole scan of the array:

(There's a small mistake in the above picture: fourth bar from the left should either be thick or drawn shorter than the first one, sorry)

Why this works: the final stack contains all elements of the input array that are not between any two larger elements (I've skipped the case of an element between two equal elements) . The solution is obviously a neighboring pair of such elements.

Here's an implementation in Python:

from collections import namedtuple  E = namedtuple('E', 'i x')  def maxrange(iterable):     stack = [E(0, None)]*2 # push sentinel values     maxsofar = None      top = lambda: stack[-1] # peek at the top element on the stack      for i, x in enumerate(iterable):         while top().x < x and top().x < maxsofar:             stack.pop()         stack.append(E(i, x)) # push         maxsofar = max(maxsofar, x)      return max(b.i-a.i for a,b in zip(stack, stack[1:])) 

Example:

>>> maxrange([2,1,3]) 2