Next Greater Element (Monotonic Stack)

Problem Statement

Given an array of integers, for each element find the next greater element — the first element to its right that is strictly larger. If no such element exists, return -1.

Next Greater Element I (LC 496): Given two arrays nums1 (subset of nums2), for each element in nums1, find its next greater element in nums2.

Next Greater Element II (LC 503): The array is circular — after the last element, it wraps around to the first. Find the next greater element for each position.

Example (LC 503 — Circular):

Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: 
- 1 → next greater is 2
- 2 → no greater element (even after wrapping)
- 1 → wraps around, next greater is 2

Constraints:

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

Difficulty: Medium

---

Pattern Recognition

• What is the input structure? An array of integers, potentially circular.
• What are we optimizing? For each element, finding the nearest greater element to the right.
• What pattern does this fit? Monotonic Stack. You maintain a stack of elements (or indices) in decreasing order. When you encounter an element larger than the stack top, that element is the "next greater" for all stack elements it exceeds.
• Why does this pattern fit? The stack ensures each element is pushed and popped at most once, giving O(n) total. The decreasing invariant means the first element that breaks it is exactly the "next greater."

---

Approach

Brute Force — Nested Loops

For each element, scan right until you find a greater element.

for i in 0..n-1:
    result[i] = -1
    for j in i+1..n-1 (wrap for circular):
        if nums[j] > nums[i]:
            result[i] = nums[j]
            break

Time: O(n^2) — for each element, scan up to n elements. Space: O(1) extra. Why insufficient: For n = 10^4, this is 10^8 in the worst case — borderline and inelegant.

Optimal — Monotonic Stack

Key Insight: Process elements from right to left (or left to right, pushing indices). Maintain a stack of candidates for "next greater." When you process element i, pop all stack elements <= nums[i] — they can never be the next greater for any element to the left of i. The stack top (if it exists) is the answer for i.

Step-by-step (right-to-left, LC 503 circular):

1. Initialize result array with -1.
2. Traverse the array twice (indices 2n-1 down to 0) to handle circularity.
3. For each i % n:
   • Pop all stack elements that are <= nums[i % n].
   • If the stack is not empty, result[i % n] = stack top.
   • Push nums[i % n] onto the stack.

function nextGreaterCircular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i from 2n-1 down to 0:
        while stack and stack.top <= nums[i % n]:
            stack.pop()
        if i < n and stack:
            result[i] = stack.top
        stack.push(nums[i % n])
    return result

Time: O(n) — each element is pushed and popped at most twice (once for each pass). Space: O(n) — stack can hold up to n elements.

---

Walkthrough

LC 503 — Circular array: nums = [3, 1, 2, 4]

Process from index 2n-1 = 7 down to 0:

i	i % n	nums[i%n]	Stack before	Pop?	Stack after pop	Result[i%n]	Stack after push
7	3	4	[]	—	[]	(skip, i>=n)	[4]
6	2	2	[4]	—	[4]	(skip, i>=n)	[4, 2]
5	1	1	[4, 2]	—	[4, 2]	(skip, i>=n)	[4, 2, 1]
4	0	3	[4, 2, 1]	pop 1, pop 2	[4]	(skip, i>=n)	[4, 3]
3	3	4	[4, 3]	pop 3, pop 4	[]	result[3] = -1	[4]
2	2	2	[4]	—	[4]	result[2] = 4	[4, 2]
1	1	1	[4, 2]	—	[4, 2]	result[1] = 2	[4, 2, 1]
0	0	3	[4, 2, 1]	pop 1, pop 2	[4]	result[0] = 4	[4, 3]

Result: [4, 2, 4, -1]

Verification:

• 3 → next greater going right and wrapping: 4 (correct)
• 1 → next greater: 2 (correct)
• 2 → next greater: 4 (correct)
• 4 → no greater element exists (correct)

---

Implementation

Next Greater Element I (LC 496)

TypeScript

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    // Build a map: for each element in nums2, what's its next greater?
    const nge = new Map<number, number>();
    const stack: number[] = [];

    for (const num of nums2) {
        // Pop elements that found their next greater (current num)
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            nge.set(stack.pop()!, num);
        }
        stack.push(num);
    }

    // Elements remaining in stack have no next greater
    return nums1.map(num => nge.get(num) ?? -1);
}

C++

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    // Build a map: for each element in nums2, what's its next greater?
    unordered_map<int, int> nge;
    stack<int> stk;

    for (int num : nums2) {
        // Pop elements that found their next greater (current num)
        while (!stk.empty() && stk.top() < num) {
            nge[stk.top()] = num;
            stk.pop();
        }
        stk.push(num);
    }

    // Elements remaining in stack have no next greater
    vector<int> result;
    for (int num : nums1) {
        result.push_back(nge.count(num) ? nge[num] : -1);
    }
    return result;
}

Next Greater Element II (LC 503 — Circular)

TypeScript

function nextGreaterElements(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = []; // Stores values (not indices) for simplicity

    // Two passes to handle circular nature
    for (let i = 2 * n - 1; i >= 0; i--) {
        const val = nums[i % n];
        // Remove all elements that aren't greater than current
        while (stack.length > 0 && stack[stack.length - 1] <= val) {
            stack.pop();
        }
        // Only record results for the first pass (i < n)
        if (i < n && stack.length > 0) {
            result[i] = stack[stack.length - 1];
        }
        stack.push(val);
    }

    return result;
}

C++

vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk; // Stores values (not indices) for simplicity

    // Two passes to handle circular nature
    for (int i = 2 * n - 1; i >= 0; i--) {
        int val = nums[i % n];
        // Remove all elements that aren't greater than current
        while (!stk.empty() && stk.top() <= val) {
            stk.pop();
        }
        // Only record results for the first pass (i < n)
        if (i < n && !stk.empty()) {
            result[i] = stk.top();
        }
        stk.push(val);
    }

    return result;
}

Watch out:

1. Using < instead of <= when popping. You need strictly greater, so pop elements that are <= current. Using < would keep equal elements on the stack, which are not "greater."
2. Circular traversal — forgetting the double pass. For LC 503, you must traverse 2n elements to let each element "see" elements after the wrap. If you only do one pass, elements near the end miss their next greater from the beginning.
3. Stack stores values vs indices. For LC 496 (two arrays), store values in a map. For LC 503, either approach works, but storing values and using the i < n guard is cleaner.

---

Complexity Analysis

	Time	Space
Brute Force (Nested Loops)	O(n^2)	O(1)
Optimal (Monotonic Stack)	O(n)	O(n)
Circular variant	O(n) (two passes = 2n operations)	O(n)

Bottleneck: Each element is pushed and popped from the stack at most once (twice in the circular variant), giving amortized O(1) per element. The stack itself can hold up to n elements in the worst case (strictly decreasing array).

---

Edge Cases

1. Strictly increasing array [1, 2, 3, 4] — Each element's next greater is the immediate next. Stack never holds more than 1 element.
2. Strictly decreasing array [4, 3, 2, 1] — No element has a next greater. Result is all -1. Stack grows to size n.
3. All equal elements [5, 5, 5] — All results are -1 (need strictly greater). Ensure <= comparison in stack.
4. Single element — Result is [-1].
5. Circular: the greatest element — Its next greater is -1 even after wrapping. All other elements should find something.
6. Negative numbers — The algorithm works identically; just ensure comparisons handle negatives correctly.

---

Related Problems

• LC 496 — Next Greater Element I — Non-circular, two arrays. Simpler variant.
• LC 503 — Next Greater Element II — Circular array variant.
• LC 739 — Daily Temperatures — "Next warmer day" — identical monotonic stack pattern but returns the distance instead of the value.
• LC 84 — Largest Rectangle in Histogram — Uses monotonic stack to find next smaller element on both sides.
• Aggressive Cows (Binary Search on Answer) — A related binary search problem often paired in Amazon interviews. Given n stalls and k cows, maximize the minimum distance between cows. Uses binary search on the answer with a greedy feasibility check.

---

What is Expected at Each Level

Junior: Solve the brute force O(n^2) approach. Understand the concept of a monotonic stack with guidance. Implement LC 496 (non-circular).

Mid-level: Immediately identify the monotonic stack pattern. Solve both LC 496 and LC 503. Explain the amortized O(n) analysis clearly. Handle edge cases without prompting.

Senior: Solve both variants quickly. Extend to "next greater on both sides" (for histogram problems). Discuss the monotonic stack as a general tool for range queries. Connect to problems like stock span, trapping rain water, and largest rectangle. Analyze cache performance of stack-based vs array-based implementations.