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

by

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:

Stack-bars

(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

Leave a Comment

tech