503. Next Greater Element II (Medium)

Problem

Given a circular integer array nums, return the next greater number for every element. In a circular array, the search wraps around to the beginning if no greater element is found before the end.

Return -1 if no greater element exists at all (only possible if all elements are equal).

Examples

• [1,2,1] → [2,-1,2]
  • 1 at index 0: next greater is 2 (index 1)
  • 2 at index 1: no greater element in the full circular scan: -1
  • 1 at index 2: wraps around to find 2 (index 1)
• [1,2,3,4,3] → [2,3,4,-1,4]
• [5,4,3,2,1] → [-1,5,5,5,5]

LeetCode 503 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force with circular wraparound

For each index, scan up to n steps forward (with wrap) looking for a strictly greater element.

Python

def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n                          # L1: O(n)
    for i in range(n):                         # L2: n iterations
        for j in range(1, n):                  # L3: up to n-1 steps per i
            k = (i + j) % n                    # L4: O(1) circular index
            if nums[k] > nums[i]:              # L5: O(1) compare
                result[i] = nums[k]
                break
    return result

TypeScript

function nextGreaterElements(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);      // L1: O(n)
    for (let i = 0; i < n; i++) {             // L2: n iterations
        for (let j = 1; j < n; j++) {         // L3: up to n-1 steps per i
            const k = (i + j) % n;            // L4: O(1) circular index
            if (nums[k] > nums[i]) { result[i] = nums[k]; break; }  // L5: O(1) compare
        }
    }
    return result;
}

Swift

final class Solution {
    func nextGreaterElements(_ nums: [Int]) -> [Int] {
        guard !nums.isEmpty else { return [] }
        return nums.indices.map { index in
            for offset in 1..<nums.count {
                let candidate = nums[(index + offset) % nums.count]
                if candidate > nums[index] { return candidate }
            }
            return -1
        }
    }
}

Complexity

• Time: $O(n²)$, each of n elements scans up to n positions.
• Space: $O(1)$ extra.

Approach 2: Double traversal with monotonic index stack (optimal)

Simulate circularity by iterating indices 0 to 2n-1 and using i % n to wrap. The first pass fills answers for straightforward cases; the second pass fills wrap-around answers.

Use a monotonic decreasing stack that stores indices (not values). When the current value exceeds the value at the stack top, the stack top has found its next-greater answer.

Python

def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)                                      # L1: O(1)
    result = [-1] * n                                  # L2: O(n) default -1
    stack = []                                         # L3: O(1) stores indices

    for i in range(2 * n):                             # L4: 2n iterations
        while stack and nums[stack[-1]] < nums[i % n]: # L5: pop answered indices
            result[stack.pop()] = nums[i % n]          # L6: O(1) amortized
        if i < n:                                      # L7: only push original indices
            stack.append(i)                            # L8: O(1) push index

    return result

TypeScript

function nextGreaterElements(nums: number[]): number[] {
    const n = nums.length;                                      // L1: O(1)
    const result = new Array(n).fill(-1);                       // L2: O(n) default -1
    const stack: number[] = [];                                 // L3: O(1) stores indices

    for (let i = 0; i < 2 * n; i++) {                          // L4: 2n iterations
        while (stack.length && nums[stack[stack.length - 1]] < nums[i % n])
            result[stack.pop()!] = nums[i % n];                 // L5-L6: O(1) amortized
        if (i < n) stack.push(i);                               // L7-L8: only push during first pass
    }

    return result;
}

Swift

final class Solution {
    func nextGreaterElements(_ nums: [Int]) -> [Int] {
        guard !nums.isEmpty else { return [] }
        var answer = Array(repeating: -1, count: nums.count)
        var stack: [Int] = []
        for index in 0..<(2 * nums.count) {
            let current = index % nums.count
            while let last = stack.last, nums[current] > nums[last] { answer[stack.removeLast()] = nums[current] }
            if index < nums.count { stack.append(current) }
        }
        return answer
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (init result)	$O(n)$	1	$O(n)$
L4 (outer loop)	$O(1)$	2n	$O(n)$
L5-L8 (stack ops)	$O(1)$ amortized	n total pushes/pops	$O(n)$ ← dominates

Each index is pushed once (guard i < n) and popped at most once. Total stack work across both passes is $O(n)$.

Complexity

• Time: $O(n)$, the 2n loop with amortized $O(1)$ stack work per step.
• Space: $O(n)$ for the result array and stack.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Circular traversal illustrated

nums = [1, 2, 1],  n=3
result= [-1,-1,-1]

i=0 (1%3=0, val=1): stack empty, push 0.  stack: [0]
i=1 (1%3=1, val=2): 2>nums[0]=1, pop 0, result[0]=2. push 1.  stack: [1]
i=2 (2%3=2, val=1): 1<nums[1]=2, just push 2.  stack: [1,2]
i=3 (3%3=0, val=1): i>=n, don't push.  1<nums[2]=1? no. stack: [1,2]
i=4 (4%3=1, val=2): i>=n, don't push.  2>nums[2]=1, pop 2, result[2]=2. stack: [1]
                                        2>nums[1]=2? no. stack: [1]
i=5 (5%3=2, val=1): i>=n, don't push.  1<nums[1]=2? yes. stack: [1]

Remaining stack: [1], result[1] stays -1.
Final: [2, -1, 2]

Key takeaways

• The “double array” trick (range(2*n) with i % n) is the standard way to simulate circularity for monotonic stack problems. No actual array duplication needed.
• Store indices (not values) in the stack when you need to write back to a result array.
• Only push during the first pass (i < n). The second pass only processes existing stack entries, not adds new ones. This keeps the total push count at n.
• Elements left on the stack after both passes have no greater element anywhere in the circle: their default -1 stands.

Related topics

• Next Greater Element I, non-circular version, hash-map lookup
• Daily Temperatures, same monotonic stack pattern
• Stacks, underlying data structure

Related concepts

• Monotonic Stack, the ordered stack pattern for nearest greater, nearest smaller, and spans.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.