LeetCode 503 - Next Greater Element II

LeetCode Problem 503

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem gives us a circular array nums, and for every element, we must find the next greater element. The phrase next greater element means the first value encountered while moving forward in the array that is strictly larger than the current number.

The key complication is that the array is circular. Normally, when searching for the next greater element, we would only move to the right. Here, if we reach the end of the array, we wrap around to the beginning and continue searching until we either find a larger number or return to the original position.

For example, consider nums = [1,2,1].

The first 1 finds 2 immediately to its right, so its answer is 2.

The 2 has no larger value anywhere in the circular traversal, so its answer is -1.

The last 1 wraps around and eventually encounters 2, so its answer is also 2.

The input is an integer array nums, where:

• nums.length ranges from 1 to 10^4
• Each value may be negative and can be as small as -10^9 or as large as 10^9

The array size constraint is particularly important. A solution that checks every possible next element for every number would take quadratic time, O(n²), which becomes inefficient when n = 10^4. We therefore need a more efficient approach.

Several edge cases are important to recognize immediately:

• A single-element array, such as [5], can never have a greater next element, so the answer must be [-1].
• Arrays where all elements are equal, such as [3,3,3], should return all -1s because no strictly larger element exists.
• A strictly decreasing array, such as [5,4,3,2,1], requires circular traversal for nearly every element.
• Arrays with duplicate values can be tricky because we are looking for a strictly greater element, not an equal one.

Approaches

Brute Force Approach

A straightforward solution is to process each element independently.

For every index i, we simulate moving forward through the circular array and check elements one by one until either:

1. We find a number greater than nums[i]
2. We return to the original index, meaning no greater number exists

Since the array is circular, we can use modulo arithmetic:

next_index = (i + step) % n

This guarantees that traversal wraps back to the beginning when necessary.

This method is correct because it directly follows the problem definition. For every element, we explicitly search for the first greater value encountered in traversal order.

However, this approach is inefficient. In the worst case, every element may scan nearly the entire array. For an array of length n, this produces O(n²) time complexity, which is too slow for larger inputs.

Optimal Approach, Monotonic Stack

The key observation is that many repeated comparisons happen in the brute-force solution.

Instead of searching independently for each element, we can process the array in a way that reuses previous work.

We use a monotonic decreasing stack to keep track of indices whose next greater element has not yet been found.

The idea works like this:

When processing a number, if it is larger than the element represented at the top of the stack, then it becomes the next greater element for that index.

Because the array is circular, we simulate traversing it twice. Iterating 2 * n times ensures every element gets a chance to look past the end of the array and wrap around.

The stack remains monotonically decreasing, meaning values represented by stack indices are stored in descending order. Whenever a larger value appears, smaller elements are resolved immediately.

This eliminates redundant scanning and reduces the time complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every next position for every element
Optimal	O(n)	O(n)	Monotonic decreasing stack with circular simulation

Algorithm Walkthrough

Optimal Algorithm Using a Monotonic Stack

1. Initialize an answer array of size n filled with -1.

We assume initially that no greater element exists. If we later find one, we overwrite the value. 2. Create an empty stack.

Instead of storing values, we store indices. Indices allow us to access both the original number and update the result array directly. 3. Traverse the array 2 * n times.

Since the array is circular, a single pass is insufficient. Iterating twice simulates wrapping around naturally.

At each iteration:

current_index = i % n
current_value = nums[current_index]

4. While the stack is not empty and the current value is greater than the element represented by the top stack index, resolve pending answers.

This means:

nums[stack[-1]] < current_value

The current value is the first larger number encountered for that index, so:

result[stack.pop()] = current_value

5. During only the first pass, push indices into the stack.

We only add indices when i < n.

This avoids duplicate entries because the second traversal exists only to simulate circular lookup. 6. Continue until all iterations finish.

Any index still in the stack never found a greater element, so its answer remains -1.

Why it works

The crucial invariant is that the stack always stores indices whose next greater element has not yet been found, and their corresponding values remain in decreasing order.

Whenever a larger value appears, it immediately resolves all smaller elements waiting on top of the stack. Since each index is pushed once and popped once, every element is processed efficiently while still preserving the correct traversal order. The second pass guarantees circular behavior by allowing elements near the end of the array to search the beginning.

Python Solution

from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack = []

        for i in range(2 * n):
            current_index = i % n
            current_value = nums[current_index]

            while stack and nums[stack[-1]] < current_value:
                index = stack.pop()
                result[index] = current_value

            if i < n:
                stack.append(current_index)

        return result

The implementation begins by creating a result array filled with -1, which represents the default assumption that no greater element exists.

The stack stores unresolved indices. We intentionally store indices instead of values because indices let us both compare against the original array and update the correct position in result.

The loop runs for 2 * n iterations to simulate circular traversal. Modulo arithmetic converts the doubled iteration into valid array positions.

Inside the loop, the while condition checks whether the current value can resolve pending smaller elements from the stack. If so, we repeatedly pop indices and assign their next greater value.

We only push indices during the first pass because each index should appear exactly once in the stack. The second pass exists only to help unresolved elements find answers through wraparound traversal.

Finally, the method returns the populated result array.

Go Solution

func nextGreaterElements(nums []int) []int {
	n := len(nums)
	result := make([]int, n)

	for i := range result {
		result[i] = -1
	}

	stack := []int{}

	for i := 0; i < 2*n; i++ {
		currentIndex := i % n
		currentValue := nums[currentIndex]

		for len(stack) > 0 &&
			nums[stack[len(stack)-1]] < currentValue {

			index := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			result[index] = currentValue
		}

		if i < n {
			stack = append(stack, currentIndex)
		}
	}

	return result
}

The Go implementation closely mirrors the Python logic.

Since Go slices are initialized with zero values, we explicitly fill result with -1. The stack is implemented as a slice of indices, where the end of the slice acts as the stack top.

Popping is done by slicing:

stack = stack[:len(stack)-1]

Go integers safely handle the problem constraints because values are within ±10^9, which easily fits inside the standard int type on modern systems.

Worked Examples

Example 1

Input:

nums = [1,2,1]

Initial state:

result = [-1,-1,-1]
stack = []

Iteration	Index	Value	Stack Before	Action	Result
0	0	1	[]	Push 0	[-1,-1,-1]
1	1	2	[0]	Pop 0, result[0]=2, push 1	[2,-1,-1]
2	2	1	[1]	Push 2	[2,-1,-1]
3	0	1	[1,2]	No pop	[2,-1,-1]
4	1	2	[1,2]	Pop 2, result[2]=2	[2,-1,2]
5	2	1	[1]	No pop	[2,-1,2]

Final output:

[2,-1,2]

Example 2

Input:

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

Initial state:

result = [-1,-1,-1,-1,-1]
stack = []

Iteration	Index	Value	Stack Before	Action	Result
0	0	1	[]	Push 0	[-1,-1,-1,-1,-1]
1	1	2	[0]	Pop 0 → 2, Push 1	[2,-1,-1,-1,-1]
2	2	3	[1]	Pop 1 → 3, Push 2	[2,3,-1,-1,-1]
3	3	4	[2]	Pop 2 → 4, Push 3	[2,3,4,-1,-1]
4	4	3	[3]	Push 4	[2,3,4,-1,-1]
5	0	1	[3,4]	No pop	[2,3,4,-1,-1]
6	1	2	[3,4]	No pop	[2,3,4,-1,-1]
7	2	3	[3,4]	No pop, equal not valid	[2,3,4,-1,-1]
8	3	4	[3,4]	Pop 4 → 4	[2,3,4,-1,4]
9	4	3	[3]	No pop	[2,3,4,-1,4]

Final output:

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

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is pushed and popped at most once
Space	O(n)	Stack and result array may store up to n elements

Although the loop runs 2 * n times, this still simplifies to O(n) because constant factors are ignored in asymptotic analysis. More importantly, each element enters and leaves the stack only once, preventing repeated work. The stack contributes linear auxiliary space in the worst case, such as a strictly decreasing array.

Test Cases

class Solution:
    def nextGreaterElements(self, nums):
        n = len(nums)
        result = [-1] * n
        stack = []

        for i in range(2 * n):
            current_index = i % n
            current_value = nums[current_index]

            while stack and nums[stack[-1]] < current_value:
                index = stack.pop()
                result[index] = current_value

            if i < n:
                stack.append(current_index)

        return result

solution = Solution()

assert solution.nextGreaterElements([1, 2, 1]) == [2, -1, 2]  # example 1
assert solution.nextGreaterElements([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]  # example 2

assert solution.nextGreaterElements([5]) == [-1]  # single element
assert solution.nextGreaterElements([3, 3, 3]) == [-1, -1, -1]  # all equal
assert solution.nextGreaterElements([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5]  # decreasing
assert solution.nextGreaterElements([1, 2, 3, 4, 5]) == [2, 3, 4, 5, -1]  # increasing
assert solution.nextGreaterElements([2, 1, 2, 4, 3]) == [4, 2, 4, -1, 4]  # mixed values
assert solution.nextGreaterElements([-2, -1, -3]) == [-1, -1, -2]  # negative values
assert solution.nextGreaterElements([1, 1, 2, 1]) == [2, 2, -1, 2]  # duplicates
assert solution.nextGreaterElements([1000000000, -1000000000]) == [-1, 1000000000]  # large values

Test	Why
[1,2,1]	Validates circular traversal
[1,2,3,4,3]	Verifies mixed increasing and decreasing behavior
[5]	Smallest valid input
[3,3,3]	Ensures equal values are not treated as greater
[5,4,3,2,1]	Tests heavy circular dependency
[1,2,3,4,5]	Confirms increasing order handling
[2,1,2,4,3]	Validates general mixed case
[-2,-1,-3]	Confirms support for negative values
[1,1,2,1]	Ensures duplicate handling is correct
[1000000000,-1000000000]	Verifies extreme constraint values

Edge Cases

Single Element Array

An array containing only one element, such as [7], can easily cause bugs if circular traversal is not handled carefully. A naive implementation might accidentally compare the element to itself and incorrectly conclude that it is the next greater value. Our implementation avoids this issue because no value is strictly greater, so the stack entry remains unresolved and the default -1 remains unchanged.

All Elements Are Equal

Consider [4,4,4]. Since the problem requires a strictly greater number, equal values do not qualify. A common mistake is accidentally using <= instead of < when comparing stack elements. Our implementation uses:

nums[stack[-1]] < current_value

which guarantees only strictly larger numbers resolve pending elements.

Strictly Decreasing Arrays

Inputs such as [5,4,3,2,1] are challenging because most elements cannot find a greater value to their right during the first pass. Without proper circular handling, the algorithm would incorrectly return all -1s. The second traversal solves this problem by allowing smaller elements to wrap around and discover 5, while 5 itself correctly remains -1.

Duplicate Peaks

Arrays like [2,1,2] can expose logical mistakes involving duplicate maximum values. The first 2 should not use the second 2 as its next greater element because equality does not count. Only values strictly larger qualify. The monotonic stack logic correctly preserves unresolved indices until a genuinely larger number appears, or leaves them as -1 if none exists.