Monotonic Stack Example: The Next Greater Value Around a Circular Array

A circular array, where the search for a larger value wraps round from the end to the start, takes the same stack with two laps of the loop. Index i runs from 0 to 2n − 1 and reads the value at i mod n, the remainder after division by n, so the second lap passes over every value again. Positions are pushed only on the first lap, while i < n; the second lap only pops and answers, so each position still waits once.

On 3 8 4 1 2, the last value, 2, has nothing larger after it in a straight line, but around the circle the 3 at the start comes next. The steps show both laps.

3 8 4 1 2
^
stack (indices): 0
answer: _ _ _ _ _

3 8 4 1 2
  ^
stack (indices): 1
answer: 8 _ _ _ _

3 8 4 1 2
    ^
stack (indices): 1 2
answer: 8 _ _ _ _

3 8 4 1 2
      ^
stack (indices): 1 2 3
answer: 8 _ _ _ _

3 8 4 1 2
        ^
stack (indices): 1 2 4
answer: 8 _ _ 2 _

3 8 4 1 2
^
stack (indices): 1 2
answer: 8 _ _ 2 3

3 8 4 1 2
  ^
stack (indices): 1
answer: 8 _ 8 2 3

3 8 4 1 2
    ^
stack (indices): 1
answer: 8 _ 8 2 3

3 8 4 1 2
      ^
stack (indices): 1
answer: 8 _ 8 2 3

3 8 4 1 2
        ^
stack (indices): 1
answer: 8 _ 8 2 3

The run prints 8 −1 8 2 3. The second lap answered index 4 with the 3 and index 2 with the 8, both found by wrapping round, and left only index 1, whose 8 is the largest value, so its answer is −1. Pushing on the second lap as well would put positions on the stack twice and could answer a position with itself.

The pass reads 2n values, and every index is still pushed once and popped at most once, so it is O(n) time and O(n) extra space. Concatenating the array with itself would work too, at the cost of a copy of n values.