LeetCode 2454 - Next Greater Element IV

The problem asks us to compute, for every element in the array, its "second greater element" to the right. For an index i, we are interested in elements positioned after i. Among those elements, we only care about values strictly greater than nums[i].

leetcodehardarraybinary-searchstacksortingheap-(priority-queue)monotonic-stack

LeetCode Problem 2454

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Stack, Sorting, Heap (Priority Queue), Monotonic Stack

Solution

Problem Understanding

The problem asks us to compute, for every element in the array, its "second greater element" to the right.

For an index i, we are interested in elements positioned after i. Among those elements, we only care about values strictly greater than nums[i].

The second greater element is defined very precisely:

  • We need an index j > i
  • nums[j] > nums[i]
  • Between i and j, there must be exactly one element greater than nums[i]

Another way to think about this is:

  • Find all elements to the right of nums[i] that are greater than it
  • Order them by position
  • The second greater element is simply the second such element encountered

For example, consider:

nums = [2,4,0,9,6]

For 2 at index 0:

  • First greater element is 4
  • Second greater element is 9

So the answer for index 0 is 9.

For 0 at index 2:

  • Greater elements to the right are 9 and 6
  • The second one encountered is 6

So the answer is 6.

If fewer than two greater elements exist to the right, the answer is -1.

The constraints are important:

  • nums.length can be up to 100000
  • A quadratic solution would perform up to 10^10 operations in the worst case, which is far too slow

This immediately tells us that we need a near linear solution, typically O(n) or O(n log n).

Several edge cases are important:

  • Arrays with all equal values, such as [3,3,3]
  • Strictly decreasing arrays, where no greater elements exist
  • Strictly increasing arrays, where many second greater elements exist
  • Duplicate values, because the condition requires strictly greater values
  • Very large arrays, which rule out nested scanning approaches

The problem guarantees:

  • All numbers are non-negative
  • Array length is at least 1
  • Values fit comfortably within standard integer types

Approaches

Brute Force Approach

The most direct solution is to process each index independently.

For every index i:

  1. Scan all elements to the right
  2. Count how many elements are greater than nums[i]
  3. Once the second greater element is found, record it
  4. If the scan finishes before finding two greater elements, return -1

For example:

nums = [2,4,0,9,6]

For index 0:

  • 4 > 2, count = 1
  • 0 ignored
  • 9 > 2, count = 2, answer = 9

This works because it directly follows the definition of the problem.

However, its performance is poor.

For each element, we may scan nearly the entire remainder of the array. With n = 100000, this becomes too slow.

Optimal Approach

The key observation is that we do not actually need to repeatedly rescan the array.

This problem resembles the classic "next greater element" problem, which is usually solved with a monotonic stack. However, here we need the second greater element, not the first.

The important insight is:

  • Some elements are still waiting for their first greater element
  • Some elements have already found their first greater element and are now waiting for their second greater element

We can track these two states separately.

We use:

  • One monotonic decreasing stack for elements waiting for their first greater element
  • Another structure for elements that already found their first greater element and are now waiting for the second

The elegant solution uses:

  • A decreasing stack called first_stack
  • Another decreasing stack called second_stack

As we process each number:

  • Elements popped from second_stack have now found their second greater element
  • Elements popped from first_stack have just found their first greater element, so they move into second_stack

This allows every element to move through the process only a small number of times, leading to linear complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Scan right side for every index
Optimal O(n) O(n) Uses two monotonic stacks

Algorithm Walkthrough

Optimal Two Stack Algorithm

  1. Initialize the result array with -1.

Every index defaults to -1 because some elements may never find a second greater element. 2. Create two stacks.

The first stack stores indices waiting for their first greater element.

The second stack stores indices that already found their first greater element and are now waiting for their second greater element. 3. Iterate through the array from left to right.

At each position, treat the current value as a possible greater element for earlier indices. 4. First, process the second stack.

While the current number is greater than the value represented by the top index in second_stack, we have found the second greater element for that index.

Record the current value in the answer array. 5. Next, process the first stack.

While the current number is greater than the value represented by the top index in first_stack, those indices have now found their first greater element.

Remove them from first_stack. 6. Transfer those removed indices into second_stack.

This means they are now waiting for their second greater element.

The transfer order matters because we want to preserve the monotonic behavior correctly. 7. Push the current index into first_stack.

The current element has not yet found even its first greater element. 8. Continue until all elements are processed. 9. Return the answer array.

Why it works

The algorithm maintains two clear invariants:

  • first_stack contains indices that have not yet encountered any greater element
  • second_stack contains indices that have encountered exactly one greater element

When a new value arrives:

  • Any index removed from second_stack has now seen exactly two greater elements, so the current value is its answer
  • Any index removed from first_stack has now seen its first greater element, so it transitions into second_stack

Each index moves through the states in order:

waiting for first greater
→ waiting for second greater
→ completed

Because every index is pushed and popped only a constant number of times, the total work is linear.

Python Solution

from typing import List

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)

        answer = [-1] * n

        first_stack = []
        second_stack = []

        for current_index, current_value in enumerate(nums):

            # Resolve second greater elements
            while second_stack and nums[second_stack[-1]] < current_value:
                index = second_stack.pop()
                answer[index] = current_value

            # Elements that just found their first greater element
            moved = []

            while first_stack and nums[first_stack[-1]] < current_value:
                moved.append(first_stack.pop())

            # Preserve correct order when moving
            while moved:
                second_stack.append(moved.pop())

            # Current element waits for first greater
            first_stack.append(current_index)

        return answer

The implementation follows the exact state transition described earlier.

The answer array is initialized with -1, which automatically handles elements that never find a second greater value.

first_stack stores indices waiting for their first greater element. The stack is maintained in decreasing order of values.

Whenever the current number is greater than the top element of first_stack, those indices have now encountered their first greater element. They are removed and temporarily stored in moved.

The temporary moved array is important because the order of insertion into second_stack matters. Reversing the order preserves the monotonic property correctly.

second_stack contains indices that already found one greater element. When the current value exceeds the top of this stack, the current value becomes the second greater element for that index.

Every index is pushed and popped at most once from each stack, which guarantees linear runtime.

Go Solution

func secondGreaterElement(nums []int) []int {
	n := len(nums)

	answer := make([]int, n)

	for i := 0; i < n; i++ {
		answer[i] = -1
	}

	firstStack := []int{}
	secondStack := []int{}

	for currentIndex, currentValue := range nums {

		// Resolve second greater elements
		for len(secondStack) > 0 &&
			nums[secondStack[len(secondStack)-1]] < currentValue {

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

			answer[index] = currentValue
		}

		moved := []int{}

		// Resolve first greater elements
		for len(firstStack) > 0 &&
			nums[firstStack[len(firstStack)-1]] < currentValue {

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

			moved = append(moved, index)
		}

		// Move into second stack in reverse order
		for len(moved) > 0 {
			secondStack = append(secondStack, moved[len(moved)-1])
			moved = moved[:len(moved)-1]
		}

		firstStack = append(firstStack, currentIndex)
	}

	return answer
}

The Go implementation mirrors the Python logic closely.

Slices are used as stacks. Appending pushes an element, and reslicing removes the top.

The result array must be explicitly initialized to -1 because Go integer slices default to 0.

There are no integer overflow concerns because the constraints fit within Go's standard int type.

Worked Examples

Example 1

nums = [2,4,0,9,6]

Initial state:

Step Current first_stack second_stack answer
Start - [] [] [-1,-1,-1,-1,-1]

Process index 0, value 2:

Step Current first_stack second_stack answer
Push 0 2 [0] [] [-1,-1,-1,-1,-1]

Process index 1, value 4:

  • 4 > 2
  • Index 0 found first greater element
  • Move 0 into second_stack
Step Current first_stack second_stack answer
After processing 4 [1] [0] [-1,-1,-1,-1,-1]

Process index 2, value 0:

Step Current first_stack second_stack answer
Push 2 0 [1,2] [0] [-1,-1,-1,-1,-1]

Process index 3, value 9:

  • 9 > 2, so index 0 gets second greater = 9
  • 9 > 0, index 2 found first greater
  • 9 > 4, index 1 found first greater
Step Current first_stack second_stack answer
After processing 9 [3] [1,2] [9,-1,-1,-1,-1]

Process index 4, value 6:

  • 6 > 0, so index 2 gets second greater = 6
  • 6 > 4, so index 1 gets second greater = 6
Step Current first_stack second_stack answer
Final 6 [3,4] [] [9,6,6,-1,-1]

Final answer:

[9,6,6,-1,-1]

Example 2

nums = [3,3]

Process index 0:

Step Current first_stack second_stack answer
Push 0 3 [0] [] [-1,-1]

Process index 1:

  • 3 is not strictly greater than 3
  • Nothing moves
Step Current first_stack second_stack answer
Final 3 [0,1] [] [-1,-1]

Final answer:

[-1,-1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is pushed and popped at most once from each stack
Space O(n) Stacks and answer array may store all indices

The runtime is linear because no index is processed excessively. Every element transitions through the stacks a constant number of times.

The space complexity is linear because, in the worst case, both stacks together may hold nearly all indices.

Test Cases

from typing import List

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        n = len(nums)

        answer = [-1] * n

        first_stack = []
        second_stack = []

        for current_index, current_value in enumerate(nums):

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

            moved = []

            while first_stack and nums[first_stack[-1]] < current_value:
                moved.append(first_stack.pop())

            while moved:
                second_stack.append(moved.pop())

            first_stack.append(current_index)

        return answer

solution = Solution()

assert solution.secondGreaterElement([2,4,0,9,6]) == [9,6,6,-1,-1]  # official example
assert solution.secondGreaterElement([3,3]) == [-1,-1]  # equal values

assert solution.secondGreaterElement([1]) == [-1]  # single element
assert solution.secondGreaterElement([1,2]) == [-1,-1]  # only one greater exists
assert solution.secondGreaterElement([1,2,3]) == [3,-1,-1]  # increasing sequence

assert solution.secondGreaterElement([5,4,3,2,1]) == [-1,-1,-1,-1,-1]  # decreasing sequence

assert solution.secondGreaterElement([1,1,1,1]) == [-1,-1,-1,-1]  # duplicates only

assert solution.secondGreaterElement([2,1,3,4]) == [4,4,-1,-1]  # multiple second greater values

assert solution.secondGreaterElement([1,5,2,6,3,7]) == [2,7,7,-1,-1,-1]  # interleaved behavior

assert solution.secondGreaterElement([10,1,2,3,4]) == [-1,3,4,-1,-1]  # large first element

assert solution.secondGreaterElement([1,3,2,4,5]) == [2,5,5,-1,-1]  # mixed ordering
Test Why
[2,4,0,9,6] Validates official example
[3,3] Ensures strict inequality is enforced
[1] Smallest possible input
[1,2] Only one greater element exists
[1,2,3] Simple increasing sequence
[5,4,3,2,1] No greater elements anywhere
[1,1,1,1] Duplicate handling
[2,1,3,4] Multiple elements resolve together
[1,5,2,6,3,7] Complex stack transitions
[10,1,2,3,4] Large leading element never resolves
[1,3,2,4,5] Mixed ordering and delayed resolution

Edge Cases

Arrays With Duplicate Values

The comparison must be strictly greater, not greater than or equal.

For example:

[3,3,3]

No element is greater than another, so every answer is -1.

A common bug is accidentally using <= instead of < when comparing stack elements. The implementation correctly uses strict inequality.

Strictly Decreasing Arrays

Consider:

[5,4,3,2,1]

No element ever encounters even a first greater value.

This means all indices remain in first_stack until the end, and the result stays entirely -1.

The implementation handles this naturally because unresolved entries are never overwritten.

Elements With Only One Greater Value

Consider:

[1,2]

The element 1 has only one greater value to its right, not two.

A buggy implementation might incorrectly treat the first greater value as the answer.

This solution explicitly separates:

  • waiting for first greater
  • waiting for second greater

An element is only assigned an answer after transitioning through both states.

Large Increasing Arrays

For arrays like:

[1,2,3,4,5,...]

Many indices quickly transition between stacks.

A naive nested loop would become quadratic.

The monotonic stack approach ensures each index moves through the system only once, preserving linear complexity even for the largest inputs allowed by the constraints.