DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Next Greater Element II

mediumStack and queue Must-do

Problem statement

You get a list of numbers, nums, arranged in a circle — so after the last element, the array wraps back around to the first one. For every element, find the first number that comes after it (searching forward, wrapping around the circle if needed) that is strictly bigger. If no such number exists anywhere in the circle, the answer for that element is -1. Return one answer per element, in the same order as the input.

Think of nums as readings taken around a ring of sensors, or a rotation schedule for a fixed set of hosts — "circular" just means that after you reach the end, the search continues from the beginning again instead of stopping.

Examples

Example 1

Input: nums = [1,2,1]

Output: [2,-1,2]

Explanation: The first 1 (index 0) looks forward and finds 2 right away. The 2 (index 1) looks forward, wraps around past the end, and finds only the first 1 again — nothing bigger than 2 anywhere in the circle, so the answer is -1. The second 1 (index 2) looks forward, wraps around, and finds 2 (the first element) as the first bigger value.

Example 2

Input: nums = [1,2,3,4,3]

Output: [2,3,4,-1,4]

Explanation: No wrapping is needed here except for the last element: 4 (index 3) is the largest value in the array, so nothing beats it even after wrapping — its answer is -1. The last 3 (index 4) wraps around and finds 4 (the first element) as the first bigger value.

Hints

Approach

Optimal: Monotonic stack, two passes

Intuition

Walk through the array's indices twice (2n steps total, using i % n to map each step back onto a real index — no need to physically build a doubled array), but go backward, from the last conceptual position to the first. Keep a stack of indices that are still "waiting" for their next greater element. Before recording an answer for the current index, pop off the stack every index whose value isn't bigger than the current one — those values can never be the answer for anything to their left, since something bigger just showed up closer to them. Whatever's left on top of the stack after that popping is the closest bigger value still ahead, which is exactly the answer. Walking backward means "ahead" in the search direction always means "already on the stack, closer to the top", which is what makes a single pass (doubled for the wraparound) enough — the brute-force approach redoes this searching from scratch for every single index.

Steps

  1. Create a result array of size n, filled with -1, and an empty stack of indices.
  2. Loop i from 2n - 1 down to 0. Compute realI = i % n (the actual index this step maps to).
  3. While the stack isn't empty and nums[stack top] <= nums[realI], pop the stack — those values are beaten by the current one and can never be anyone's answer that appears before realI in the search order.
  4. If i < n (this is the "real" pass, not just priming the stack from the second lap), set result[realI] to nums[top of stack] if the stack isn't empty, or -1 if it is.
  5. Push realI onto the stack regardless — it might still be the answer for something further back.
  6. After the loop, return the result array.

Dry run

nums = [1, 2, 1] (n = 3, so i runs from 5 down to 0)

i realI pop while top ≤ nums[realI] i < n? result[realI] stack after push
5 2 stack empty, nothing to pop no — [2]
4 1 nums[2]=1 ≤ nums[1]=2 → pop 2; stack empty no — [1]
3 0 nums[1]=2 > nums[0]=1, stop no — [1, 0]
2 2 nums[0]=1 ≤ nums[2]=1 → pop 0; nums[1]=2 > 1, stop yes result[2] = nums[1] = 2 [1, 2]
1 1 nums[2]=1 ≤ nums[1]=2 → pop 2; stack empty yes result[1] = -1 [1]
0 0 nums[1]=2 > nums[0]=1, stop yes result[0] = nums[1] = 2 [1, 0]

Final result: [2, -1, 2] — the same answer as the brute-force approach, in one pass over 2n steps instead of n separate searches.

Edge cases: a single-element array pushes and pops around an empty stack the whole time, correctly leaving result[0] = -1. The first n steps of the loop (where i >= n) exist only to "prime" the stack with the second half of the circle before any answer is recorded — that's what lets the very first real elements still see values that are circularly ahead of them.

Complexity

Time O(n) — Each index is pushed onto the stack at most once across the whole traversal (2n steps total, since the array is walked twice), and popped at most once, so the total work across every push and pop combined is O(n).

Space O(n) — The result array plus a stack that can hold up to n indices.

from typing import List


class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack = []  # indices whose next greater element hasn't been found yet
        for i in range(2 * n - 1, -1, -1):
            real_i = i % n
            while stack and nums[stack[-1]] <= nums[real_i]:
                stack.pop()
            if i < n:
                result[real_i] = nums[stack[-1]] if stack else -1
            stack.append(real_i)
        return result


if __name__ == "__main__":
    print(Solution().nextGreaterElements([1, 2, 1]))
    print(Solution().nextGreaterElements([1, 2, 3, 4, 3]))

Follow-up questions

Run essentially the same algorithm, but walk the doubled range forward (from 0 to 2n - 1) instead of backward, since "previous" means the stack needs to hold indices that come before the current one in search order — which is what a forward walk naturally builds up. Everything else about the push/pop logic against a monotonic stack stays the same.

Only the first full period needs the doubled 2n treatment — after that, the next-greater answer for any element is identical to the corresponding element in the first period, since the values just repeat. Compute the answers once for a single period using the stack approach, then map every other position back to its position within that period (index % period) to reuse the same answer, without ever materializing the full array.

Frequently asked questions

The stack needs to hold values that are still "ahead" (in search order) of whatever index is currently being answered. Walking backward means that by the time you reach a given index, the stack already contains every index that comes after it in the search direction — including ones from the wrapped-around second lap. Walking forward would need a different (and messier) bookkeeping scheme to get the same guarantee.

The first n steps (where i >= n, so i < n is false) don't record any answers — they only push the "second lap" of indices onto the stack so that elements near the start of the array can already see circularly-ahead values when their turn comes. Only the second n steps (i from n - 1 down to 0) actually write into the result array.

The problem asks for the first strictly greater value. If a stacked value is equal to the current one, it still isn't strictly greater than it, so it can never be the answer for anything — popping it now (rather than leaving it to possibly be picked later) is correct and also avoids ever recording an equal value as if it were a valid "next greater" answer.

A circular buffer or a round-robin rotation of workers/hosts is common in scheduling and load balancing, and "find the next entry that's bigger than me" comes up in maintaining priority within a ring — for example, finding the next node in a hash ring with more available capacity than the current one, wrapping around if needed.