Data Structures & AlgorithmsMonotonic Stacks

Monotonic Stacks — Advanced Pattern

LevelIntermediate

Duration50 mins

TopicMonotonic Stacks

3 / 4

Next Greater Element Problem

The Iconic Monotonic Stack Problem

If there is one problem that perfectly captures the essence of monotonic stacks, it's the Next Greater Element (NGE) problem. This deceptively simple problem appears in countless variations across coding interviews, competitive programming contests, and real-world applications.

Understanding NGE thoroughly isn't just about solving one problem—it's about internalizing a pattern that unlocks solutions to dozens of related problems. The intuition you build here will transfer directly to stock span problems, temperature problems, histogram problems, and more.

Let's master this fundamental problem in all its variations.

What You Will Learn

By the end of this page, you will be able to: (1) solve the basic NGE problem optimally, (2) handle circular arrays, (3) solve NGE II where elements may appear multiple times, (4) extend the pattern to 'days until warmer temperature' style problems, and (5) recognize NGE patterns disguised in other contexts.

The Basic Problem Statement

Problem Statement:

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

Example:

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

Explanation:

nums[0] = 2 → First greater element to right is 4 (at index 3)
nums[1] = 1 → First greater element to right is 2 (at index 2)
nums[2] = 2 → First greater element to right is 4 (at index 3)
nums[3] = 4 → No greater element to right → -1
nums[4] = 3 → No greater element to right → -1

Brute Force Baseline

The naive approach uses two nested loops: for each element, scan all elements to its right until finding a greater one. This is O(n²). Our goal is O(n) using a monotonic stack.

nge-brute-force.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Brute Force: O(n²) time, O(1) extra space
 */
function nextGreaterBrute(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) {
                result[i] = nums[j];
                break;  // Found first greater, stop
            }
        }
    }
    
    return result;
}

The Optimal Monotonic Stack Solution

We use a monotonically decreasing stack to solve this in O(n) time. The key insight:

Elements waiting for their 'next greater' are stored in decreasing order. When a greater element arrives, it resolves all smaller waiting elements at once.

The algorithm:

Process elements left to right
Maintain a stack of indices with values in decreasing order
For each new element, pop all smaller elements (they found their answer)
Push the current index
At the end, remaining indices have no greater element

nge-optimal.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Optimal Solution: O(n) time, O(n) space
 * Uses a monotonically decreasing stack
 */
function nextGreaterElement(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];  // Stack of indices
    
    for (let i = 0; i < n; i++) {
        // While stack is not empty and current element is greater than stack top
        while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
            // Pop the index - current element is its next greater
            const poppedIndex = stack.pop()!;
            result[poppedIndex] = nums[i];
        }
        // Push current index onto stack
        stack.push(i);
    }
    
    // Elements remaining in stack have no next greater element
    // result already initialized to -1, so we're done
    
    return result;
}
 
// Example trace for [2, 1, 2, 4, 3]:
// i=0: stack=[], push 0 → stack=[0]
// i=1: nums[0]=2 > nums[1]=1, push 1 → stack=[0,1]
// i=2: nums[1]=1 < nums[2]=2, pop 1, result[1]=2
//      nums[0]=2 == nums[2]=2 (not <), push 2 → stack=[0,2]
// i=3: nums[2]=2 < nums[3]=4, pop 2, result[2]=4
//      nums[0]=2 < nums[3]=4, pop 0, result[0]=4
//      push 3 → stack=[3]
// i=4: nums[3]=4 > nums[4]=3, push 4 → stack=[3,4]
// End: indices 3,4 have no NGE → result[3]=-1, result[4]=-1
// Final: [4, 2, 4, -1, -1]

Complexity Analysis:

Time Complexity: O(n) — Each element is pushed exactly once and popped at most once.
Space Complexity: O(n) — Stack can hold up to n elements (in strictly decreasing input like [5,4,3,2,1]).

Why This Works:

The stack maintains elements that are still 'waiting' for their next greater element. They must be in decreasing order because:

If A comes before B and A < B, then B would have been A's next greater, and A would have been popped.
If A > B, both can wait—a future element might be greater than both.

When a new element X arrives:

All elements smaller than X have now found their answer (X is it!)
X joins the waiting list (push onto stack)

Alternative: Processing Right to Left

There's an alternative approach that processes the array from right to left. This is conceptually different but equally valid:

Idea: For each element, look at the 'future' (elements to the right) that we've already processed. The stack holds potential answers, not elements waiting for answers.

nge-right-to-left.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Right-to-Left approach
 * Stack holds potential "next greater" candidates
 */
function nextGreaterRightToLeft(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];  // Stack of VALUES (not indices)
    
    // Process from right to left
    for (let i = n - 1; i >= 0; i--) {
        // Pop elements that can't be the answer for current
        // (they're smaller or equal to current)
        while (stack.length > 0 && stack[stack.length - 1] <= nums[i]) {
            stack.pop();
        }
        
        // If stack non-empty, top is the next greater element
        if (stack.length > 0) {
            result[i] = stack[stack.length - 1];
        }
        
        // Push current element - it might be NGE for elements to the left
        stack.push(nums[i]);
    }
    
    return result;
}
 
// This approach is also O(n) time and O(n) space
// The stack now represents "candidates to the right" in increasing order
// (smaller elements are popped because they're hidden behind larger ones)

Comparing the Two Approaches:

Aspect	Left-to-Right	Right-to-Left
Stack contains	Elements waiting for NGE	Candidates for being NGE
When answer found	At pop time	After popping smaller elements
Stack order	Decreasing	Increasing
Mental model	'Who's still waiting?'	'Who could be my answer?'

Both are valid; choose based on which mental model resonates with you or which fits the problem variant better.

When Right-to-Left Helps

The right-to-left approach is particularly intuitive when you're building the answer while you have 'visibility' of the right side. Some people find it easier to think: 'Given what I know is to my right, what's my answer?' versus 'I'll wait until someone comes who is greater.'

Circular Array Variant (NGE II)

Problem Statement:

Given a circular array, find the next greater element for each position. The array is circular, meaning after the last element, we wrap around to the first element.

Example:

Input:  [1, 2, 1]
Output: [2, -1, 2]

Explanation:

nums[0] = 1 → Moving right: 2 is greater → answer is 2
nums[1] = 2 → Moving right: 1, then wrap to 1 → nothing greater → -1
nums[2] = 1 → Wrap around: 1, 2 → 2 is greater → answer is 2

Key Insight:

We can simulate a circular array by processing the array twice (or virtually creating nums + nums). This ensures every element 'sees' all potential candidates.

The clever part: we use indices modulo n to avoid actually creating a doubled array.

nge-circular.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Next Greater Element in Circular Array
 * LeetCode 503: Next Greater Element II
 */
function nextGreaterCircular(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];  // Stack of indices
    
    // Process the array twice (2n iterations)
    // This simulates the circular nature
    for (let i = 0; i < 2 * n; i++) {
        // Use modulo to wrap around
        const currentIdx = i % n;
        const currentVal = nums[currentIdx];
        
        // Same logic as before: pop smaller elements
        while (stack.length > 0 && nums[stack[stack.length - 1]] < currentVal) {
            const poppedIdx = stack.pop()!;
            result[poppedIdx] = currentVal;
        }
        
        // Only push during the first pass (i < n)
        // Second pass is just for finding NGE, not adding new candidates
        if (i < n) {
            stack.push(currentIdx);
        }
    }
    
    return result;
}
 
// Example trace for [1, 2, 1]:
// First pass (i = 0,1,2):
//   i=0: push 0 → stack=[0]
//   i=1: nums[0]=1 < nums[1]=2, pop 0, result[0]=2; push 1 → stack=[1]
//   i=2: nums[1]=2 > nums[2]=1, push 2 → stack=[1,2]
// 
// Second pass (i = 3,4,5 → indices 0,1,2):
//   i=3 (idx 0): nums[2]=1 < nums[0]=1? No. nums[1]=2 < nums[0]=1? No.
//   i=4 (idx 1): nums[2]=1 < nums[1]=2, pop 2, result[2]=2
//                nums[1]=2 < nums[1]=2? No (equal, not less)
//   i=5 (idx 2): nothing pops
// 
// Final: [2, -1, 2]

Why Process Twice?

In the first pass, elements are added to the stack. Some may not find their NGE because it's 'before' them in the array. The second pass revisits all elements, allowing these stuck elements to potentially find an NGE from the 'wrapped around' portion. We don't push during the second pass because those indices are already represented.

Complexity:

Time: O(n) — Even though we iterate 2n times, each element is pushed once and popped at most once.
Space: O(n) — Stack can hold up to n elements.

Daily Temperatures: NGE with Distance

Problem Statement (LeetCode 739):

Given an array of daily temperatures, return an array where each element tells you how many days you would have to wait until a warmer temperature. If there is no future day with a warmer temperature, put 0.

Example:

Input:  [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1,  1,  4,  2,  1,  1,  0,  0]

This is the NGE problem in disguise! Instead of finding the value of the next greater element, we find the distance to it.

daily-temperatures.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Daily Temperatures
 * LeetCode 739
 * 
 * This is NGE but we return DISTANCE instead of VALUE
 */
function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const result = new Array(n).fill(0);  // 0 means no warmer day
    const stack: number[] = [];  // Stack of indices
    
    for (let i = 0; i < n; i++) {
        // Pop all days with lower temperature
        while (stack.length > 0 && 
               temperatures[stack[stack.length - 1]] < temperatures[i]) {
            const coldDay = stack.pop()!;
            // The answer is the DISTANCE, not the value
            result[coldDay] = i - coldDay;
        }
        stack.push(i);
    }
    
    // Days remaining in stack never see a warmer day → result stays 0
    
    return result;
}
 
// Example: [73, 74, 75, 71, 69, 72, 76, 73]
// 
// i=0 (73): push 0 → stack=[0]
// i=1 (74): 73<74, pop 0, result[0]=1-0=1; push 1 → stack=[1]
// i=2 (75): 74<75, pop 1, result[1]=2-1=1; push 2 → stack=[2]
// i=3 (71): 75>71, push 3 → stack=[2,3]
// i=4 (69): 71>69, push 4 → stack=[2,3,4]
// i=5 (72): 69<72, pop 4, result[4]=5-4=1
//           71<72, pop 3, result[3]=5-3=2
//           75>72, push 5 → stack=[2,5]
// i=6 (76): 72<76, pop 5, result[5]=6-5=1
//           75<76, pop 2, result[2]=6-2=4
//           push 6 → stack=[6]
// i=7 (73): 76>73, push 7 → stack=[6,7]
// End: indices 6,7 have no warmer day → result[6]=0, result[7]=0
// 
// Final: [1, 1, 4, 2, 1, 1, 0, 0]

Pattern Recognition

Whenever you see 'how many days/steps until X,' think monotonic stack. The key is recognizing that 'first occurrence of condition' maps to 'next greater/smaller.' The answer is a distance when indices are involved, a value when only values matter.

Stock Span: Previous Greater in Disguise

Problem Statement (LeetCode 901):

The stock span is defined as the maximum number of consecutive days (starting from today and going backwards) for which the stock price was less than or equal to today's price.

Example:

Prices: [100, 80, 60, 70, 60, 75, 85]
Span:   [1,   1,  1,  2,  1,  4,  6]

Explanation for index 5 (price 75):

Looking back: 60, 70, 60, 80... stop at 80 (80 > 75)
Days where price ≤ 75: indices 4, 3, 2 (values 60, 70, 60), plus today
Span = 4

This is a previous greater element problem! The span is current_index - index_of_previous_greater + 1 (or current_index + 1 if no previous greater exists).

stock-span.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Stock Span Problem
 * LeetCode 901
 * 
 * Uses a monotonically DECREASING stack to find previous greater
 */
function calculateSpan(prices: number[]): number[] {
    const n = prices.length;
    const span = new Array(n);
    const stack: number[] = [];  // Stack of indices with decreasing prices
    
    for (let i = 0; i < n; i++) {
        // Pop all days with price <= today's price
        // (they're 'covered' by today and won't be previous greater for future days)
        while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
            stack.pop();
        }
        
        // Span = distance to previous greater day (or distance to start if none)
        if (stack.length === 0) {
            span[i] = i + 1;  // No previous greater, span covers all days so far
        } else {
            span[i] = i - stack[stack.length - 1];  // Distance to previous greater
        }
        
        stack.push(i);
    }
    
    return span;
}
 
// Example: [100, 80, 60, 70, 60, 75, 85]
// 
// i=0 (100): stack empty, span[0]=0+1=1; push 0 → stack=[0]
// i=1 (80):  100>80, span[1]=1-0=1; push 1 → stack=[0,1]
// i=2 (60):  80>60, span[2]=2-1=1; push 2 → stack=[0,1,2]
// i=3 (70):  60<=70, pop 2; 80>70, span[3]=3-1=2; push 3 → stack=[0,1,3]
// i=4 (60):  70>60, span[4]=4-3=1; push 4 → stack=[0,1,3,4]
// i=5 (75):  60<=75, pop 4; 70<=75, pop 3; 80>75, span[5]=5-1=4; push 5 → stack=[0,1,5]
// i=6 (85):  75<=85, pop 5; 80<=85, pop 1; 100>85, span[6]=6-0=6; push 6 → stack=[0,6]
// 
// Final: [1, 1, 1, 2, 1, 4, 6]

The Key Insight

Stock span asks 'how far back can I go before hitting a strictly greater price?' This is exactly 'what's my previous greater element?' combined with distance calculation. The monotonically decreasing stack naturally provides the previous greater via the stack top before pushing.

NGE I: Querying from Another Array

Problem Statement (LeetCode 496):

Given two arrays nums1 and nums2 where nums1 is a subset of nums2, find the next greater element for each element of nums1 in nums2. The next greater element of x in nums2 is the first element to the right of x in nums2 that is greater.

Example:

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]

Explanation:

4 is in nums2 at index 2. To its right: [2]. No greater element. → -1
1 is in nums2 at index 0. To its right: [3, 4, 2]. First greater: 3. → 3
2 is in nums2 at index 3. To its right: []. No greater element. → -1

nge-query.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Next Greater Element I
 * LeetCode 496
 * 
 * Precompute NGE for all elements in nums2,
 * then answer queries from nums1
 */
function nextGreaterElementI(nums1: number[], nums2: number[]): number[] {
    // Step 1: Build a map of element → its next greater in nums2
    const ngeMap = new Map<number, number>();
    const stack: number[] = [];  // Stack of values (nums2 has unique elements)
    
    for (const num of nums2) {
        // Pop elements smaller than current
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            const smaller = stack.pop()!;
            ngeMap.set(smaller, num);  // 'num' is NGE for 'smaller'
        }
        stack.push(num);
    }
    
    // Elements remaining in stack have no NGE
    while (stack.length > 0) {
        ngeMap.set(stack.pop()!, -1);
    }
    
    // Step 2: Answer queries from nums1
    return nums1.map(num => ngeMap.get(num) ?? -1);
}
 
// Example:
// nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
// 
// Processing nums2:
//   1: push → stack=[1]
//   3: 1<3, pop 1, ngeMap[1]=3; push → stack=[3]
//   4: 3<4, pop 3, ngeMap[3]=4; push → stack=[4]
//   2: 4>2, push → stack=[4,2]
//   End: ngeMap[4]=-1, ngeMap[2]=-1
// 
// ngeMap = {1→3, 3→4, 4→-1, 2→-1}
// 
// Answering nums1:
//   4 → -1
//   1 → 3
//   2 → -1
// 
// Result: [-1, 3, -1]

When to Precompute

When you have multiple queries against the same data, precompute the answers into a lookup structure (Map/HashMap). This is O(n + m) total instead of O(n × m) if you processed each query independently.

Summary: Mastering NGE Patterns

The Next Greater Element problem family is vast. Let's consolidate what you've learned:

NGE Problem Variants Summary
Problem Variant	Key Modification	Complexity
Basic NGE	Standard decreasing stack	O(n)
NGE Circular	Process array twice (2n iterations)	O(n)
NGE Distance (Daily Temps)	Return distance i - poppedIdx	O(n)
Previous Greater (Stock Span)	Answer from stack top before push	O(n)
NGE with Queries	Precompute into HashMap	O(n + m)
Next Smaller	Use increasing stack instead	O(n)

Problem Recognition Signals

•'First element to the right that...' → Next greater/smaller with forward processing
•'First element to the left that...' → Previous greater/smaller (check stack top)
•'How many days/steps until...' → NGE with distance calculation
•'Maximum consecutive...' → Often previous greater (span-style)
•'Circular array' → Process 2n elements with modulo
•'For each element in subset...' → Precompute with HashMap

What's Next:

We've mastered the NGE family of problems. In the final page of this module, we'll tackle the Histogram Area problem—perhaps the most famous 'hard' monotonic stack problem. It combines everything we've learned and demonstrates the true power of this technique.

Page Complete

You've now mastered the Next Greater Element problem and its many variants. You can solve basic NGE, circular arrays, distance calculations, stock spans, and query-based problems. You recognize the patterns and know which variant applies to which problem type.

3 / 4

Loading learning content...

Data Structures & AlgorithmsMonotonic Stacks

Monotonic Stacks — Advanced Pattern

LevelIntermediate

Duration50 mins

TopicMonotonic Stacks

3 / 4

Next Greater Element Problem

The Iconic Monotonic Stack Problem

Let's master this fundamental problem in all its variations.

What You Will Learn

The Basic Problem Statement

Problem Statement:

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

Example:

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

Explanation:

nums[0] = 2 → First greater element to right is 4 (at index 3)
nums[1] = 1 → First greater element to right is 2 (at index 2)
nums[2] = 2 → First greater element to right is 4 (at index 3)
nums[3] = 4 → No greater element to right → -1
nums[4] = 3 → No greater element to right → -1

Brute Force Baseline

The naive approach uses two nested loops: for each element, scan all elements to its right until finding a greater one. This is O(n²). Our goal is O(n) using a monotonic stack.

nge-brute-force.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Brute Force: O(n²) time, O(1) extra space
 */
function nextGreaterBrute(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[j] > nums[i]) {
                result[i] = nums[j];
                break;  // Found first greater, stop
            }
        }
    }
    
    return result;
}

The Optimal Monotonic Stack Solution

We use a monotonically decreasing stack to solve this in O(n) time. The key insight:

Elements waiting for their 'next greater' are stored in decreasing order. When a greater element arrives, it resolves all smaller waiting elements at once.

The algorithm:

Process elements left to right
Maintain a stack of indices with values in decreasing order
For each new element, pop all smaller elements (they found their answer)
Push the current index
At the end, remaining indices have no greater element

nge-optimal.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Optimal Solution: O(n) time, O(n) space
 * Uses a monotonically decreasing stack
 */
function nextGreaterElement(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];  // Stack of indices
    
    for (let i = 0; i < n; i++) {
        // While stack is not empty and current element is greater than stack top
        while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
            // Pop the index - current element is its next greater
            const poppedIndex = stack.pop()!;
            result[poppedIndex] = nums[i];
        }
        // Push current index onto stack
        stack.push(i);
    }
    
    // Elements remaining in stack have no next greater element
    // result already initialized to -1, so we're done
    
    return result;
}
 
// Example trace for [2, 1, 2, 4, 3]:
// i=0: stack=[], push 0 → stack=[0]
// i=1: nums[0]=2 > nums[1]=1, push 1 → stack=[0,1]
// i=2: nums[1]=1 < nums[2]=2, pop 1, result[1]=2
//      nums[0]=2 == nums[2]=2 (not <), push 2 → stack=[0,2]
// i=3: nums[2]=2 < nums[3]=4, pop 2, result[2]=4
//      nums[0]=2 < nums[3]=4, pop 0, result[0]=4
//      push 3 → stack=[3]
// i=4: nums[3]=4 > nums[4]=3, push 4 → stack=[3,4]
// End: indices 3,4 have no NGE → result[3]=-1, result[4]=-1
// Final: [4, 2, 4, -1, -1]

Complexity Analysis:

Time Complexity: O(n) — Each element is pushed exactly once and popped at most once.
Space Complexity: O(n) — Stack can hold up to n elements (in strictly decreasing input like [5,4,3,2,1]).

Why This Works:

The stack maintains elements that are still 'waiting' for their next greater element. They must be in decreasing order because:

If A comes before B and A < B, then B would have been A's next greater, and A would have been popped.
If A > B, both can wait—a future element might be greater than both.

When a new element X arrives:

All elements smaller than X have now found their answer (X is it!)
X joins the waiting list (push onto stack)

Alternative: Processing Right to Left

There's an alternative approach that processes the array from right to left. This is conceptually different but equally valid:

Idea: For each element, look at the 'future' (elements to the right) that we've already processed. The stack holds potential answers, not elements waiting for answers.

nge-right-to-left.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Right-to-Left approach
 * Stack holds potential "next greater" candidates
 */
function nextGreaterRightToLeft(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];  // Stack of VALUES (not indices)
    
    // Process from right to left
    for (let i = n - 1; i >= 0; i--) {
        // Pop elements that can't be the answer for current
        // (they're smaller or equal to current)
        while (stack.length > 0 && stack[stack.length - 1] <= nums[i]) {
            stack.pop();
        }
        
        // If stack non-empty, top is the next greater element
        if (stack.length > 0) {
            result[i] = stack[stack.length - 1];
        }
        
        // Push current element - it might be NGE for elements to the left
        stack.push(nums[i]);
    }
    
    return result;
}
 
// This approach is also O(n) time and O(n) space
// The stack now represents "candidates to the right" in increasing order
// (smaller elements are popped because they're hidden behind larger ones)

Comparing the Two Approaches:

Aspect	Left-to-Right	Right-to-Left
Stack contains	Elements waiting for NGE	Candidates for being NGE
When answer found	At pop time	After popping smaller elements
Stack order	Decreasing	Increasing
Mental model	'Who's still waiting?'	'Who could be my answer?'

Both are valid; choose based on which mental model resonates with you or which fits the problem variant better.

When Right-to-Left Helps

Circular Array Variant (NGE II)

Problem Statement:

Given a circular array, find the next greater element for each position. The array is circular, meaning after the last element, we wrap around to the first element.

Example:

Input:  [1, 2, 1]
Output: [2, -1, 2]

Explanation:

nums[0] = 1 → Moving right: 2 is greater → answer is 2
nums[1] = 2 → Moving right: 1, then wrap to 1 → nothing greater → -1
nums[2] = 1 → Wrap around: 1, 2 → 2 is greater → answer is 2

Key Insight:

We can simulate a circular array by processing the array twice (or virtually creating nums + nums). This ensures every element 'sees' all potential candidates.

The clever part: we use indices modulo n to avoid actually creating a doubled array.

nge-circular.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Next Greater Element in Circular Array
 * LeetCode 503: Next Greater Element II
 */
function nextGreaterCircular(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];  // Stack of indices
    
    // Process the array twice (2n iterations)
    // This simulates the circular nature
    for (let i = 0; i < 2 * n; i++) {
        // Use modulo to wrap around
        const currentIdx = i % n;
        const currentVal = nums[currentIdx];
        
        // Same logic as before: pop smaller elements
        while (stack.length > 0 && nums[stack[stack.length - 1]] < currentVal) {
            const poppedIdx = stack.pop()!;
            result[poppedIdx] = currentVal;
        }
        
        // Only push during the first pass (i < n)
        // Second pass is just for finding NGE, not adding new candidates
        if (i < n) {
            stack.push(currentIdx);
        }
    }
    
    return result;
}
 
// Example trace for [1, 2, 1]:
// First pass (i = 0,1,2):
//   i=0: push 0 → stack=[0]
//   i=1: nums[0]=1 < nums[1]=2, pop 0, result[0]=2; push 1 → stack=[1]
//   i=2: nums[1]=2 > nums[2]=1, push 2 → stack=[1,2]
// 
// Second pass (i = 3,4,5 → indices 0,1,2):
//   i=3 (idx 0): nums[2]=1 < nums[0]=1? No. nums[1]=2 < nums[0]=1? No.
//   i=4 (idx 1): nums[2]=1 < nums[1]=2, pop 2, result[2]=2
//                nums[1]=2 < nums[1]=2? No (equal, not less)
//   i=5 (idx 2): nothing pops
// 
// Final: [2, -1, 2]

Why Process Twice?

Complexity:

Time: O(n) — Even though we iterate 2n times, each element is pushed once and popped at most once.
Space: O(n) — Stack can hold up to n elements.

Daily Temperatures: NGE with Distance

Problem Statement (LeetCode 739):

Example:

Input:  [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1,  1,  4,  2,  1,  1,  0,  0]

This is the NGE problem in disguise! Instead of finding the value of the next greater element, we find the distance to it.

daily-temperatures.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Daily Temperatures
 * LeetCode 739
 * 
 * This is NGE but we return DISTANCE instead of VALUE
 */
function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const result = new Array(n).fill(0);  // 0 means no warmer day
    const stack: number[] = [];  // Stack of indices
    
    for (let i = 0; i < n; i++) {
        // Pop all days with lower temperature
        while (stack.length > 0 && 
               temperatures[stack[stack.length - 1]] < temperatures[i]) {
            const coldDay = stack.pop()!;
            // The answer is the DISTANCE, not the value
            result[coldDay] = i - coldDay;
        }
        stack.push(i);
    }
    
    // Days remaining in stack never see a warmer day → result stays 0
    
    return result;
}
 
// Example: [73, 74, 75, 71, 69, 72, 76, 73]
// 
// i=0 (73): push 0 → stack=[0]
// i=1 (74): 73<74, pop 0, result[0]=1-0=1; push 1 → stack=[1]
// i=2 (75): 74<75, pop 1, result[1]=2-1=1; push 2 → stack=[2]
// i=3 (71): 75>71, push 3 → stack=[2,3]
// i=4 (69): 71>69, push 4 → stack=[2,3,4]
// i=5 (72): 69<72, pop 4, result[4]=5-4=1
//           71<72, pop 3, result[3]=5-3=2
//           75>72, push 5 → stack=[2,5]
// i=6 (76): 72<76, pop 5, result[5]=6-5=1
//           75<76, pop 2, result[2]=6-2=4
//           push 6 → stack=[6]
// i=7 (73): 76>73, push 7 → stack=[6,7]
// End: indices 6,7 have no warmer day → result[6]=0, result[7]=0
// 
// Final: [1, 1, 4, 2, 1, 1, 0, 0]

Pattern Recognition

Stock Span: Previous Greater in Disguise

Problem Statement (LeetCode 901):

The stock span is defined as the maximum number of consecutive days (starting from today and going backwards) for which the stock price was less than or equal to today's price.

Example:

Prices: [100, 80, 60, 70, 60, 75, 85]
Span:   [1,   1,  1,  2,  1,  4,  6]

Explanation for index 5 (price 75):

Looking back: 60, 70, 60, 80... stop at 80 (80 > 75)
Days where price ≤ 75: indices 4, 3, 2 (values 60, 70, 60), plus today
Span = 4

This is a previous greater element problem! The span is current_index - index_of_previous_greater + 1 (or current_index + 1 if no previous greater exists).

stock-span.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Stock Span Problem
 * LeetCode 901
 * 
 * Uses a monotonically DECREASING stack to find previous greater
 */
function calculateSpan(prices: number[]): number[] {
    const n = prices.length;
    const span = new Array(n);
    const stack: number[] = [];  // Stack of indices with decreasing prices
    
    for (let i = 0; i < n; i++) {
        // Pop all days with price <= today's price
        // (they're 'covered' by today and won't be previous greater for future days)
        while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
            stack.pop();
        }
        
        // Span = distance to previous greater day (or distance to start if none)
        if (stack.length === 0) {
            span[i] = i + 1;  // No previous greater, span covers all days so far
        } else {
            span[i] = i - stack[stack.length - 1];  // Distance to previous greater
        }
        
        stack.push(i);
    }
    
    return span;
}
 
// Example: [100, 80, 60, 70, 60, 75, 85]
// 
// i=0 (100): stack empty, span[0]=0+1=1; push 0 → stack=[0]
// i=1 (80):  100>80, span[1]=1-0=1; push 1 → stack=[0,1]
// i=2 (60):  80>60, span[2]=2-1=1; push 2 → stack=[0,1,2]
// i=3 (70):  60<=70, pop 2; 80>70, span[3]=3-1=2; push 3 → stack=[0,1,3]
// i=4 (60):  70>60, span[4]=4-3=1; push 4 → stack=[0,1,3,4]
// i=5 (75):  60<=75, pop 4; 70<=75, pop 3; 80>75, span[5]=5-1=4; push 5 → stack=[0,1,5]
// i=6 (85):  75<=85, pop 5; 80<=85, pop 1; 100>85, span[6]=6-0=6; push 6 → stack=[0,6]
// 
// Final: [1, 1, 1, 2, 1, 4, 6]

The Key Insight

NGE I: Querying from Another Array

Problem Statement (LeetCode 496):

Example:

nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]

Explanation:

4 is in nums2 at index 2. To its right: [2]. No greater element. → -1
1 is in nums2 at index 0. To its right: [3, 4, 2]. First greater: 3. → 3
2 is in nums2 at index 3. To its right: []. No greater element. → -1

nge-query.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Next Greater Element I
 * LeetCode 496
 * 
 * Precompute NGE for all elements in nums2,
 * then answer queries from nums1
 */
function nextGreaterElementI(nums1: number[], nums2: number[]): number[] {
    // Step 1: Build a map of element → its next greater in nums2
    const ngeMap = new Map<number, number>();
    const stack: number[] = [];  // Stack of values (nums2 has unique elements)
    
    for (const num of nums2) {
        // Pop elements smaller than current
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            const smaller = stack.pop()!;
            ngeMap.set(smaller, num);  // 'num' is NGE for 'smaller'
        }
        stack.push(num);
    }
    
    // Elements remaining in stack have no NGE
    while (stack.length > 0) {
        ngeMap.set(stack.pop()!, -1);
    }
    
    // Step 2: Answer queries from nums1
    return nums1.map(num => ngeMap.get(num) ?? -1);
}
 
// Example:
// nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
// 
// Processing nums2:
//   1: push → stack=[1]
//   3: 1<3, pop 1, ngeMap[1]=3; push → stack=[3]
//   4: 3<4, pop 3, ngeMap[3]=4; push → stack=[4]
//   2: 4>2, push → stack=[4,2]
//   End: ngeMap[4]=-1, ngeMap[2]=-1
// 
// ngeMap = {1→3, 3→4, 4→-1, 2→-1}
// 
// Answering nums1:
//   4 → -1
//   1 → 3
//   2 → -1
// 
// Result: [-1, 3, -1]

When to Precompute

Summary: Mastering NGE Patterns

The Next Greater Element problem family is vast. Let's consolidate what you've learned:

NGE Problem Variants Summary
Problem Variant	Key Modification	Complexity
Basic NGE	Standard decreasing stack	O(n)
NGE Circular	Process array twice (2n iterations)	O(n)
NGE Distance (Daily Temps)	Return distance i - poppedIdx	O(n)
Previous Greater (Stock Span)	Answer from stack top before push	O(n)
NGE with Queries	Precompute into HashMap	O(n + m)
Next Smaller	Use increasing stack instead	O(n)

Problem Recognition Signals

•'First element to the right that...' → Next greater/smaller with forward processing
•'First element to the left that...' → Previous greater/smaller (check stack top)
•'How many days/steps until...' → NGE with distance calculation
•'Maximum consecutive...' → Often previous greater (span-style)
•'Circular array' → Process 2n elements with modulo
•'For each element in subset...' → Precompute with HashMap

What's Next:

Page Complete

3 / 4