Monotonic Stacks - Learning Module

Loading content...

0/279

Monotonically Increasing vs Decreasing

The Two Flavors of Monotonicity

In the previous page, we established what a monotonic stack is and why the monotonic property enables efficient solutions. Now we face a practical question that trips up many programmers: which variant do I use?

There are two fundamental types of monotonic stacks: monotonically increasing and monotonically decreasing. Choosing the wrong one doesn't just produce incorrect results—it produces results that look plausible but are subtly wrong, making debugging frustratingly difficult.

This page will give you complete clarity on both variants, eliminating all ambiguity. By the end, choosing the right variant will become second nature.

What You Will Learn

By the end of this page, you will be able to: (1) precisely define both stack variants, (2) understand which variant solves which class of problems, (3) implement both variants correctly, and (4) avoid common confusion between the two.

Precise Definitions

Let's establish unambiguous definitions. In both cases, we're describing the order from the bottom of the stack to the top.

Monotonically Increasing Stack:

Elements are arranged in non-decreasing order from bottom to top.
The smallest element is at the bottom.
The largest element is at the top.
When pushing a new element, we pop all elements that are greater than the incoming element.

Monotonically Decreasing Stack:

Elements are arranged in non-increasing order from bottom to top.
The largest element is at the bottom.
The smallest element is at the top.
When pushing a new element, we pop all elements that are smaller than the incoming element.

Terminology Warning

Some resources define these terms differently, or use confusing names like 'next greater element stack.' Always verify definitions by examining the invariant: what order is maintained, and what triggers a pop? The name matters less than understanding the mechanics.

Side-by-Side Comparison of Monotonic Stack Variants
Property	Monotonically Increasing	Monotonically Decreasing
Order (bottom → top)	Non-decreasing (↑)	Non-increasing (↓)
Bottom element	Minimum	Maximum
Top element	Maximum (or recent)	Minimum (or recent)
Pop condition	stack.top() > incoming	stack.top() < incoming
What pops find	Next Smaller Element	Next Greater Element
What remains find	Previous Smaller Element	Previous Greater Element

Reading the Table:

The last two rows are crucial. When an element is popped, the incoming element that caused the pop is its answer. When an element remains on the stack after processing, the element below it (if any) provides different information.

This duality—popped elements vs remaining elements—is often exploited to answer multiple related questions in a single pass.

Monotonically Increasing Stack: Deep Dive

Let's thoroughly examine the monotonically increasing stack. The invariant is:

At all times, stack[i] ≤ stack[i+1] for all adjacent pairs (bottom to top).

To maintain this, when pushing element x, we pop all elements greater than x. After pushing, x sits on top of an element that is ≤ x (or the stack was empty).

increasing-stack-implementation.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
/**
 * Monotonically Increasing Stack Implementation
 * Finds the NEXT SMALLER element for each position
 */
function findNextSmaller(arr: number[]): number[] {
    const n = arr.length;
    const result = new Array(n).fill(-1);  // -1 indicates no smaller element
    const stack: number[] = [];  // Stack stores INDICES
    
    for (let i = 0; i < n; i++) {
        // Pop all elements GREATER than current
        // These elements have found their "next smaller" = arr[i]
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            const poppedIndex = stack.pop()!;
            result[poppedIndex] = arr[i];  // or store i for index
        }
        stack.push(i);
    }
    
    // Elements remaining in stack have no next smaller element
    // result already initialized to -1, so nothing to do
    
    return result;
}
 
// Example usage:
// arr = [4, 8, 5, 2, 25]
// result = [2, 5, 2, -1, -1]
// Explanation:
//   4 → next smaller is 2
//   8 → next smaller is 5
//   5 → next smaller is 2
//   2 → no smaller element to right
//   25 → no smaller element to right

Trace Example: arr = [4, 8, 5, 2, 25]

Let's trace through step by step:

Step-by-Step Trace: Increasing Stack Finding Next Smaller
i	arr[i]	Stack Before	Action	Stack After	Answers
0	4	[]	Push 0	[0]	—
1	8	[0]	4 < 8 (no pop), Push 1	[0, 1]	—
2	5	[0, 1]	8 > 5 → Pop 1, answer[1]=5; 4 < 5, Push 2	[0, 2]	answer[1]=5
3	2	[0, 2]	5 > 2 → Pop 2, answer[2]=2; 4 > 2 → Pop 0, answer[0]=2; Push 3	[3]	answer[2]=2, answer[0]=2
4	25	[3]	2 < 25 (no pop), Push 4	[3, 4]	—
End	—	[3, 4]	Indices 3,4 remain: no next smaller	[]	answer[3]=-1, answer[4]=-1

Key Observations:

When element 5 arrives at index 2, it triggers a pop of index 1 (value 8) because 8 > 5. Element 5 becomes the 'next smaller' for element 8.
When element 2 arrives at index 3, it triggers two pops: first index 2 (value 5) and then index 0 (value 4). Element 2 is smaller than both, so it's the answer for both.
Element 25 at index 4 doesn't trigger any pops because 25 > 2. Both elements 2 and 25 remain at the end with no 'next smaller' to their right.
The stack maintains increasing order throughout: [4], [4, 8], [4, 5], [2], [2, 25].

Monotonically Decreasing Stack: Deep Dive

Now let's examine the monotonically decreasing stack. The invariant is:

At all times, stack[i] ≥ stack[i+1] for all adjacent pairs (bottom to top).

To maintain this, when pushing element x, we pop all elements smaller than x. After pushing, x sits on top of an element that is ≥ x (or the stack was empty).

decreasing-stack-implementation.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
/**
 * Monotonically Decreasing Stack Implementation
 * Finds the NEXT GREATER element for each position
 */
function findNextGreater(arr: number[]): number[] {
    const n = arr.length;
    const result = new Array(n).fill(-1);  // -1 indicates no greater element
    const stack: number[] = [];  // Stack stores INDICES
    
    for (let i = 0; i < n; i++) {
        // Pop all elements SMALLER than current
        // These elements have found their "next greater" = arr[i]
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            const poppedIndex = stack.pop()!;
            result[poppedIndex] = arr[i];  // or store i for index
        }
        stack.push(i);
    }
    
    // Elements remaining in stack have no next greater element
    // result already initialized to -1, so nothing to do
    
    return result;
}
 
// Example usage:
// arr = [4, 5, 2, 25]
// result = [5, 25, 25, -1]
// Explanation:
//   4 → next greater is 5
//   5 → next greater is 25
//   2 → next greater is 25
//   25 → no greater element to right

Trace Example: arr = [4, 5, 2, 25]

Step-by-Step Trace: Decreasing Stack Finding Next Greater
i	arr[i]	Stack Before	Action	Stack After	Answers
0	4	[]	Push 0	[0]	—
1	5	[0]	4 < 5 → Pop 0, answer[0]=5; Push 1	[1]	answer[0]=5
2	2	[1]	5 > 2 (no pop), Push 2	[1, 2]	—
3	25	[1, 2]	2 < 25 → Pop 2, answer[2]=25; 5 < 25 → Pop 1, answer[1]=25; Push 3	[3]	answer[2]=25, answer[1]=25
End	—	[3]	Index 3 remains: no next greater	[]	answer[3]=-1

Key Observations:

When element 5 arrives at index 1, it immediately pops index 0 (value 4) because 4 < 5. Element 5 is the 'next greater' for element 4.
When element 2 arrives at index 2, no pop occurs because 5 > 2. Element 2 is waiting for something greater than itself.
When element 25 arrives at index 3, it triggers two pops: first index 2 (value 2) and then index 1 (value 5). Element 25 is greater than both, so it's the answer for both.
The stack maintains decreasing order throughout: [4], [5], [5, 2], [25].

The Mirror Symmetry

Notice the beautiful symmetry between the two variants:

Increasing Stack	Decreasing Stack
Pop when `top > incoming`	Pop when `top < incoming`
Finds next smaller	Finds next greater
Smallest at bottom	Largest at bottom
Largest at top	Smallest at top

The variants are exact mirrors of each other. Once you deeply understand one, you understand the other—just flip the comparison operator and the problem it solves.

The Mnemonic:

Increasing stack increases toward the top → pops things that are too big → finds next smaller
Decreasing stack decreases toward the top → pops things that are too small → finds next greater

The Pop is the Answer

In both variants, remember: the element that causes a pop IS the answer for the popped element. If you pop because the incoming element is smaller, then the incoming element is the 'next smaller.' If you pop because the incoming element is greater, then the incoming element is the 'next greater.' This is the invariant that makes the algorithm correct.

Finding Previous Elements

So far we've focused on finding the next greater/smaller element. But what about the previous greater/smaller element—the first element to the left that satisfies the condition?

Here's the elegant insight: the same stack structure answers both questions simultaneously.

When we're about to push element x at index i onto an increasing stack, the element currently at the top of the stack (if any) has a special property: it's the previous smaller element for index i.

Why?

The stack contains elements that:

Appeared before index i (they were pushed earlier)
Haven't been popped yet (they're still relevant)
Maintain increasing order (smaller elements below, larger above)

The top element is the most recent element smaller than some elements we've seen—specifically, it would have been popped if anything smaller had come after it. Since x didn't pop it (the pop condition is top > x, and we're about to push), we know top ≤ x. The top is the first element to the left of i that is ≤ current element.

previous-and-next.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
/**
 * Find BOTH previous smaller and next smaller in one pass
 * using a monotonically increasing stack
 */
function findPreviousAndNextSmaller(arr: number[]): {
    previousSmaller: number[];
    nextSmaller: number[];
} {
    const n = arr.length;
    const previousSmaller = new Array(n).fill(-1);
    const nextSmaller = new Array(n).fill(-1);
    const stack: number[] = [];  // stores indices
    
    for (let i = 0; i < n; i++) {
        // Pop elements greater than current - they found next smaller
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            const poppedIndex = stack.pop()!;
            nextSmaller[poppedIndex] = i;  // current index is next smaller
        }
        
        // Before pushing, stack top is previous smaller (if exists)
        if (stack.length > 0) {
            previousSmaller[i] = stack[stack.length - 1];
        }
        
        stack.push(i);
    }
    
    return { previousSmaller, nextSmaller };
}
 
// Example: arr = [3, 7, 8, 4]
// previousSmaller = [-1, 0, 1, 0]  (indices)
// nextSmaller = [3, 3, 3, -1]  (indices)
// 
// Element 3 (idx 0): no prev smaller, next smaller at idx 3 (value 4... wait, 4>3!)
// [Correction: 4 is not < 3, so next smaller for 3 is actually -1]

Complete Picture

Using both variants, we can find all four relationships: next greater, next smaller, previous greater, previous smaller. A monotonically increasing stack gives us next smaller (via pops) and previous smaller (via remaining top). A monotonically decreasing stack gives us next greater (via pops) and previous greater (via remaining top).

Complete Reference: What Each Stack Variant Provides
Stack Type	Popped Elements Learn	Current Element Learns
Monotonically Increasing	Next Smaller Element	Previous Smaller Element (from stack top before push)
Monotonically Decreasing	Next Greater Element	Previous Greater Element (from stack top before push)

Strict vs Non-Strict Monotonicity

A subtle but important distinction: should we use strict inequality (< or >) or non-strict inequality (≤ or ≥) in our pop condition?

The choice depends on how the problem defines 'greater' or 'smaller':

Strictly Greater (most common):

Pop condition: arr[stack.top()] < arr[i] (strict inequality)
Equal elements do NOT trigger pops
Equal elements stack on each other
Handles duplicate values by treating equals as 'not greater'

Greater or Equal:

Pop condition: arr[stack.top()] <= arr[i] (non-strict)
Equal elements DO trigger pops
Only the rightmost of equal elements remains
Useful when 'strictly greater' excludes equals

strict-vs-nonstrict.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
// Example: arr = [2, 3, 3, 4]
// Looking for "next strictly greater element"
 
// With STRICT inequality (<):
// Process 2: push 0
// Process 3: 2 < 3 → pop 0, answer[0]=3; push 1
// Process 3: 3 is NOT < 3 → push 2 (equals don't pop)
// Process 4: 3 < 4 → pop 2, answer[2]=4; 3 < 4 → pop 1, answer[1]=4; push 3
// Result: [3, 4, 4, -1]
 
// With NON-STRICT inequality (<=):
// Process 2: push 0
// Process 3: 2 <= 3 → pop 0, answer[0]=3; push 1
// Process 3: 3 <= 3 → pop 1, answer[1]=3; push 2
// Process 4: 3 <= 4 → pop 2, answer[2]=4; push 3
// Result: [3, 3, 4, -1]
// Note: index 1 gets answer 3, meaning the second 3 is "next greater or equal"
 
function nextGreater(arr: number[], strict: boolean = true): number[] {
    const n = arr.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];
    
    for (let i = 0; i < n; i++) {
        const condition = strict
            ? arr[stack[stack.length - 1]] < arr[i]
            : arr[stack[stack.length - 1]] <= arr[i];
        
        while (stack.length > 0 && condition) {
            result[stack.pop()!] = arr[i];
        }
        stack.push(i);
    }
    
    return result;
}

Read the Problem Carefully

The difference between strict and non-strict is often the difference between a correct solution and a wrong answer. Problems may use phrases like 'first element greater than,' 'first element at least as large,' or 'next element that exceeds.' Parse these carefully to determine which inequality to use.

Common Pitfalls and Debugging

Having taught monotonic stacks to hundreds of engineers, I've observed the same mistakes repeatedly. Here are the most common pitfalls and how to avoid them:

Common Mistakes

•Wrong stack type: Using increasing when you need decreasing, or vice versa. Always ask: 'What comparison triggers a pop, and what does that pop represent?'
•Storing values instead of indices: Most problems need to know where the answer is, not just what it is. Always store indices; access values via arr[stack.top()].
•Forgetting remaining elements: Elements left on the stack at the end have no answer (return -1 or handle appropriately). Don't forget to process them.
•Wrong inequality direction: Using > when you need >=, or < when you need <=. This affects handling of duplicates.
•Off-by-one errors: Especially when calculating distances. Distance to next greater is nextGreaterIndex - currentIndex, not just nextGreaterIndex.
•Incorrect stack initialization: Starting with elements pre-pushed (like a sentinel) can help some problems but cause bugs in others.

Debugging Strategy:

When your solution isn't working:

Trace manually on a small example (3-4 elements). Write out the stack contents at each step.
Verify the invariant: Is the stack actually monotonic after each operation?
Check when answers are recorded: Are you recording the answer for the popped element or the pushed element?
Examine edge cases: Empty array, single element, all equal elements, all ascending, all descending.
Print debugging: Output (index, value, stack_contents) at each step.

The Ultimate Test

When unsure which variant to use, implement both and run them on a small example where you know the answer. See which one produces correct results. This takes less time than debugging a wrong approach for an hour.

Summary: The Decision Framework

Let's solidify your understanding with a decision framework:

Decision Framework

•Identify the relationship: Are you looking for 'greater' or 'smaller' elements?
•Identify the direction: Are you looking 'forward' (next) or 'backward' (previous)?
•Choose the variant: Next greater = decreasing stack. Next smaller = increasing stack. Previous = use the stack top before pushing.
•Choose the inequality: Strictly greater uses <, Strictly smaller uses >. Include equals? Add = to the operator.
•Store indices: Unless you absolutely only need values, store indices for flexibility.

Quick Reference: Which Stack for Which Problem
Problem	Stack Type	Pop Condition
Next Greater Element	Monotonically Decreasing	stack.top() < incoming
Next Smaller Element	Monotonically Increasing	stack.top() > incoming
Previous Greater Element	Monotonically Decreasing	(check top before push)
Previous Smaller Element	Monotonically Increasing	(check top before push)

What's Next:

With a solid understanding of both variants, we're ready to apply them to classic problems. In the next page, we'll tackle the Next Greater Element problem in depth—the most iconic monotonic stack problem and a gateway to understanding more complex applications.

Page Complete

You now understand the precise mechanics of both monotonically increasing and monotonically decreasing stacks. You know which variant solves which class of problems, how to find both next and previous elements, and how to debug common mistakes. You're ready to apply these tools to real problems.

Monotonically Increasing vs Decreasing

The Two Flavors of Monotonicity

This page will give you complete clarity on both variants, eliminating all ambiguity. By the end, choosing the right variant will become second nature.

What You Will Learn

Precise Definitions

Let's establish unambiguous definitions. In both cases, we're describing the order from the bottom of the stack to the top.

Monotonically Increasing Stack:

Elements are arranged in non-decreasing order from bottom to top.
The smallest element is at the bottom.
The largest element is at the top.
When pushing a new element, we pop all elements that are greater than the incoming element.

Monotonically Decreasing Stack:

Elements are arranged in non-increasing order from bottom to top.
The largest element is at the bottom.
The smallest element is at the top.
When pushing a new element, we pop all elements that are smaller than the incoming element.

Terminology Warning

Side-by-Side Comparison of Monotonic Stack Variants
Property	Monotonically Increasing	Monotonically Decreasing
Order (bottom → top)	Non-decreasing (↑)	Non-increasing (↓)
Bottom element	Minimum	Maximum
Top element	Maximum (or recent)	Minimum (or recent)
Pop condition	stack.top() > incoming	stack.top() < incoming
What pops find	Next Smaller Element	Next Greater Element
What remains find	Previous Smaller Element	Previous Greater Element

Reading the Table:

This duality—popped elements vs remaining elements—is often exploited to answer multiple related questions in a single pass.

Monotonically Increasing Stack: Deep Dive

Let's thoroughly examine the monotonically increasing stack. The invariant is:

At all times, stack[i] ≤ stack[i+1] for all adjacent pairs (bottom to top).

To maintain this, when pushing element x, we pop all elements greater than x. After pushing, x sits on top of an element that is ≤ x (or the stack was empty).

increasing-stack-implementation.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
/**
 * Monotonically Increasing Stack Implementation
 * Finds the NEXT SMALLER element for each position
 */
function findNextSmaller(arr: number[]): number[] {
    const n = arr.length;
    const result = new Array(n).fill(-1);  // -1 indicates no smaller element
    const stack: number[] = [];  // Stack stores INDICES
    
    for (let i = 0; i < n; i++) {
        // Pop all elements GREATER than current
        // These elements have found their "next smaller" = arr[i]
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            const poppedIndex = stack.pop()!;
            result[poppedIndex] = arr[i];  // or store i for index
        }
        stack.push(i);
    }
    
    // Elements remaining in stack have no next smaller element
    // result already initialized to -1, so nothing to do
    
    return result;
}
 
// Example usage:
// arr = [4, 8, 5, 2, 25]
// result = [2, 5, 2, -1, -1]
// Explanation:
//   4 → next smaller is 2
//   8 → next smaller is 5
//   5 → next smaller is 2
//   2 → no smaller element to right
//   25 → no smaller element to right

Trace Example: arr = [4, 8, 5, 2, 25]

Let's trace through step by step:

Step-by-Step Trace: Increasing Stack Finding Next Smaller
i	arr[i]	Stack Before	Action	Stack After	Answers
0	4	[]	Push 0	[0]	—
1	8	[0]	4 < 8 (no pop), Push 1	[0, 1]	—
2	5	[0, 1]	8 > 5 → Pop 1, answer[1]=5; 4 < 5, Push 2	[0, 2]	answer[1]=5
3	2	[0, 2]	5 > 2 → Pop 2, answer[2]=2; 4 > 2 → Pop 0, answer[0]=2; Push 3	[3]	answer[2]=2, answer[0]=2
4	25	[3]	2 < 25 (no pop), Push 4	[3, 4]	—
End	—	[3, 4]	Indices 3,4 remain: no next smaller	[]	answer[3]=-1, answer[4]=-1

Key Observations:

When element 5 arrives at index 2, it triggers a pop of index 1 (value 8) because 8 > 5. Element 5 becomes the 'next smaller' for element 8.
When element 2 arrives at index 3, it triggers two pops: first index 2 (value 5) and then index 0 (value 4). Element 2 is smaller than both, so it's the answer for both.
Element 25 at index 4 doesn't trigger any pops because 25 > 2. Both elements 2 and 25 remain at the end with no 'next smaller' to their right.
The stack maintains increasing order throughout: [4], [4, 8], [4, 5], [2], [2, 25].

Monotonically Decreasing Stack: Deep Dive

Now let's examine the monotonically decreasing stack. The invariant is:

At all times, stack[i] ≥ stack[i+1] for all adjacent pairs (bottom to top).

To maintain this, when pushing element x, we pop all elements smaller than x. After pushing, x sits on top of an element that is ≥ x (or the stack was empty).

decreasing-stack-implementation.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
/**
 * Monotonically Decreasing Stack Implementation
 * Finds the NEXT GREATER element for each position
 */
function findNextGreater(arr: number[]): number[] {
    const n = arr.length;
    const result = new Array(n).fill(-1);  // -1 indicates no greater element
    const stack: number[] = [];  // Stack stores INDICES
    
    for (let i = 0; i < n; i++) {
        // Pop all elements SMALLER than current
        // These elements have found their "next greater" = arr[i]
        while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
            const poppedIndex = stack.pop()!;
            result[poppedIndex] = arr[i];  // or store i for index
        }
        stack.push(i);
    }
    
    // Elements remaining in stack have no next greater element
    // result already initialized to -1, so nothing to do
    
    return result;
}
 
// Example usage:
// arr = [4, 5, 2, 25]
// result = [5, 25, 25, -1]
// Explanation:
//   4 → next greater is 5
//   5 → next greater is 25
//   2 → next greater is 25
//   25 → no greater element to right

Trace Example: arr = [4, 5, 2, 25]

Step-by-Step Trace: Decreasing Stack Finding Next Greater
i	arr[i]	Stack Before	Action	Stack After	Answers
0	4	[]	Push 0	[0]	—
1	5	[0]	4 < 5 → Pop 0, answer[0]=5; Push 1	[1]	answer[0]=5
2	2	[1]	5 > 2 (no pop), Push 2	[1, 2]	—
3	25	[1, 2]	2 < 25 → Pop 2, answer[2]=25; 5 < 25 → Pop 1, answer[1]=25; Push 3	[3]	answer[2]=25, answer[1]=25
End	—	[3]	Index 3 remains: no next greater	[]	answer[3]=-1

Key Observations:

When element 5 arrives at index 1, it immediately pops index 0 (value 4) because 4 < 5. Element 5 is the 'next greater' for element 4.
When element 2 arrives at index 2, no pop occurs because 5 > 2. Element 2 is waiting for something greater than itself.
When element 25 arrives at index 3, it triggers two pops: first index 2 (value 2) and then index 1 (value 5). Element 25 is greater than both, so it's the answer for both.
The stack maintains decreasing order throughout: [4], [5], [5, 2], [25].

The Mirror Symmetry

Notice the beautiful symmetry between the two variants:

Increasing Stack	Decreasing Stack
Pop when `top > incoming`	Pop when `top < incoming`
Finds next smaller	Finds next greater
Smallest at bottom	Largest at bottom
Largest at top	Smallest at top

The variants are exact mirrors of each other. Once you deeply understand one, you understand the other—just flip the comparison operator and the problem it solves.

The Mnemonic:

Increasing stack increases toward the top → pops things that are too big → finds next smaller
Decreasing stack decreases toward the top → pops things that are too small → finds next greater

The Pop is the Answer

Finding Previous Elements

So far we've focused on finding the next greater/smaller element. But what about the previous greater/smaller element—the first element to the left that satisfies the condition?

Here's the elegant insight: the same stack structure answers both questions simultaneously.

Why?

The stack contains elements that:

Appeared before index i (they were pushed earlier)
Haven't been popped yet (they're still relevant)
Maintain increasing order (smaller elements below, larger above)

previous-and-next.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
/**
 * Find BOTH previous smaller and next smaller in one pass
 * using a monotonically increasing stack
 */
function findPreviousAndNextSmaller(arr: number[]): {
    previousSmaller: number[];
    nextSmaller: number[];
} {
    const n = arr.length;
    const previousSmaller = new Array(n).fill(-1);
    const nextSmaller = new Array(n).fill(-1);
    const stack: number[] = [];  // stores indices
    
    for (let i = 0; i < n; i++) {
        // Pop elements greater than current - they found next smaller
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            const poppedIndex = stack.pop()!;
            nextSmaller[poppedIndex] = i;  // current index is next smaller
        }
        
        // Before pushing, stack top is previous smaller (if exists)
        if (stack.length > 0) {
            previousSmaller[i] = stack[stack.length - 1];
        }
        
        stack.push(i);
    }
    
    return { previousSmaller, nextSmaller };
}
 
// Example: arr = [3, 7, 8, 4]
// previousSmaller = [-1, 0, 1, 0]  (indices)
// nextSmaller = [3, 3, 3, -1]  (indices)
// 
// Element 3 (idx 0): no prev smaller, next smaller at idx 3 (value 4... wait, 4>3!)
// [Correction: 4 is not < 3, so next smaller for 3 is actually -1]

Complete Picture

Complete Reference: What Each Stack Variant Provides
Stack Type	Popped Elements Learn	Current Element Learns
Monotonically Increasing	Next Smaller Element	Previous Smaller Element (from stack top before push)
Monotonically Decreasing	Next Greater Element	Previous Greater Element (from stack top before push)

Strict vs Non-Strict Monotonicity

A subtle but important distinction: should we use strict inequality (< or >) or non-strict inequality (≤ or ≥) in our pop condition?

The choice depends on how the problem defines 'greater' or 'smaller':

Strictly Greater (most common):

Pop condition: arr[stack.top()] < arr[i] (strict inequality)
Equal elements do NOT trigger pops
Equal elements stack on each other
Handles duplicate values by treating equals as 'not greater'

Greater or Equal:

Pop condition: arr[stack.top()] <= arr[i] (non-strict)
Equal elements DO trigger pops
Only the rightmost of equal elements remains
Useful when 'strictly greater' excludes equals

strict-vs-nonstrict.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
// Example: arr = [2, 3, 3, 4]
// Looking for "next strictly greater element"
 
// With STRICT inequality (<):
// Process 2: push 0
// Process 3: 2 < 3 → pop 0, answer[0]=3; push 1
// Process 3: 3 is NOT < 3 → push 2 (equals don't pop)
// Process 4: 3 < 4 → pop 2, answer[2]=4; 3 < 4 → pop 1, answer[1]=4; push 3
// Result: [3, 4, 4, -1]
 
// With NON-STRICT inequality (<=):
// Process 2: push 0
// Process 3: 2 <= 3 → pop 0, answer[0]=3; push 1
// Process 3: 3 <= 3 → pop 1, answer[1]=3; push 2
// Process 4: 3 <= 4 → pop 2, answer[2]=4; push 3
// Result: [3, 3, 4, -1]
// Note: index 1 gets answer 3, meaning the second 3 is "next greater or equal"
 
function nextGreater(arr: number[], strict: boolean = true): number[] {
    const n = arr.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];
    
    for (let i = 0; i < n; i++) {
        const condition = strict
            ? arr[stack[stack.length - 1]] < arr[i]
            : arr[stack[stack.length - 1]] <= arr[i];
        
        while (stack.length > 0 && condition) {
            result[stack.pop()!] = arr[i];
        }
        stack.push(i);
    }
    
    return result;
}

Read the Problem Carefully

Common Pitfalls and Debugging

Having taught monotonic stacks to hundreds of engineers, I've observed the same mistakes repeatedly. Here are the most common pitfalls and how to avoid them:

Common Mistakes

•Wrong stack type: Using increasing when you need decreasing, or vice versa. Always ask: 'What comparison triggers a pop, and what does that pop represent?'
•Storing values instead of indices: Most problems need to know where the answer is, not just what it is. Always store indices; access values via arr[stack.top()].
•Forgetting remaining elements: Elements left on the stack at the end have no answer (return -1 or handle appropriately). Don't forget to process them.
•Wrong inequality direction: Using > when you need >=, or < when you need <=. This affects handling of duplicates.
•Off-by-one errors: Especially when calculating distances. Distance to next greater is nextGreaterIndex - currentIndex, not just nextGreaterIndex.
•Incorrect stack initialization: Starting with elements pre-pushed (like a sentinel) can help some problems but cause bugs in others.

Debugging Strategy:

When your solution isn't working:

Trace manually on a small example (3-4 elements). Write out the stack contents at each step.
Verify the invariant: Is the stack actually monotonic after each operation?
Check when answers are recorded: Are you recording the answer for the popped element or the pushed element?
Examine edge cases: Empty array, single element, all equal elements, all ascending, all descending.
Print debugging: Output (index, value, stack_contents) at each step.

The Ultimate Test

Summary: The Decision Framework

Let's solidify your understanding with a decision framework:

Decision Framework

•Identify the relationship: Are you looking for 'greater' or 'smaller' elements?
•Identify the direction: Are you looking 'forward' (next) or 'backward' (previous)?
•Choose the variant: Next greater = decreasing stack. Next smaller = increasing stack. Previous = use the stack top before pushing.
•Choose the inequality: Strictly greater uses <, Strictly smaller uses >. Include equals? Add = to the operator.
•Store indices: Unless you absolutely only need values, store indices for flexibility.

Quick Reference: Which Stack for Which Problem
Problem	Stack Type	Pop Condition
Next Greater Element	Monotonically Decreasing	stack.top() < incoming
Next Smaller Element	Monotonically Increasing	stack.top() > incoming
Previous Greater Element	Monotonically Decreasing	(check top before push)
Previous Smaller Element	Monotonically Increasing	(check top before push)

What's Next:

Page Complete