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 ?

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:

- The largest from the left (i.e. no larger or equal element between the start of the array and the element)
- 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