Next Greater Element II

Medium#503

The array is a circle: after the last number comes the first one again. For every number, find the first greater number going forward around the circle; if there is none, the answer is -1. Our example: [6, 2, 5, 1, 3] gives [-1, 5, 6, 3, 6].

503 Next Greater Element IIWalkthrough · 1×

Example: [6, 2, 5, 1, 3] in a circle. i runs over the array twice and j = i mod n is the real index; under the numbers are the answers, and the stack keeps the indices still waiting.

0612253143numsanswerstack—
not reachednums[j], the current numberwaiting on the stacktop being checkednext greater found

n = 5

01/57
restart · back · play · step
Speed
1function nextGreaterElements(nums):
2 n = len(nums)
3 answer = list of n times -1
4 stack = empty stack // indices still waiting
5 for i from 0 to 2 * n - 1:
6 j = i mod n
7 while stack not empty and nums[j] > nums[top]:
8 answer[pop from stack] = nums[j]
9 if i < n:
10 push j onto stack
11 return answer
state
n
5
answer
–
stack
–
i
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Going around the circle from any index, the next greater number is at most n − 1 steps away. Two laps cover that for every index, the last ones included.
  2. The first lap pushes every index once. The second lap only answers the indices still waiting: it pushes nothing, so no index is answered twice and none waits for itself.
  3. Whatever is left on the stack after two laps is the largest number, maybe repeated: nothing in the whole circle beats it, so -1 is right.

Complexity

Time O(n): 2n steps of the loop, and each index is pushed once and popped at most once. Memory O(n) for the stack and the answer.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.