Next Smaller Element Using Stack — Monotonic Increasing Stack Pattern

The Next Smaller Element is the mirror image of Next Greater Element. Instead of finding the first larger value to the right, you find the first smaller one. The trick is flipping the monotonic stack from decreasing to increasing.

The Problem

Given an array, for each element find the next smaller element — the first element to its right that is strictly smaller. If none exists, return -1.

Input:  [4, 8, 5, 2, 10, 3]
Output: [2, 5, 2, -1, 3, -1]

Explanation:
  4  → next smaller is 2
  8  → next smaller is 5
  5  → next smaller is 2
  2  → nothing smaller to the right → -1
  10 → next smaller is 3
  3  → nothing smaller to the right → -1

Brute Force — O(n^2)

def next_smaller_brute(arr):
    """For each element scan right — O(n^2) time."""
    n = len(arr)
    result = [-1] * n
    for i in range(n):
        for j in range(i + 1, n):
            if arr[j] < arr[i]:
                result[i] = arr[j]
                break
    return result

This works but is too slow for large inputs. We need the stack approach.

Why a Monotonic Increasing Stack?

For Next Greater we kept a decreasing stack — elements waiting for something bigger. For Next Smaller we flip the invariant: we keep an increasing stack — elements waiting for something smaller.

Problem	Stack Type	Pop When
Next Greater	Decreasing	stack[-1] < current
Next Smaller	Increasing	stack[-1] > current

The key rule: pop elements from the stack that are greater than the current element, because the current element is the answer (next smaller) for each popped element.

Optimal Solution — O(n)

Left-to-right approach (natural for “next smaller to the right”)

def next_smaller_element(arr):
    """
    For each element, find the next smaller element to its right.
    Uses a monotonic increasing stack.
    Time: O(n) — each element pushed and popped at most once.
    Space: O(n) — for the stack and result array.
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices; values at those indices are increasing

    for i in range(n):
        # Pop all elements bigger than arr[i]
        while stack and arr[stack[-1]] > arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

Right-to-left approach (alternative)

def next_smaller_rtl(arr):
    """Right-to-left scan — stack holds candidates."""
    n = len(arr)
    result = [-1] * n
    stack = []  # stores values

    for i in range(n - 1, -1, -1):
        # Remove elements >= current (can't be next smaller)
        while stack and stack[-1] >= arr[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(arr[i])

    return result

Both approaches are O(n) time and O(n) space. The left-to-right version is slightly more intuitive for most people.

Step-by-Step Trace

Let us trace next_smaller_element([4, 8, 5, 2, 10, 3]) (left-to-right):

i=0, val=4:  stack=[]         → push 0               stack=[0]
i=1, val=8:  stack=[0]        → 4<8, no pop, push 1   stack=[0,1]
i=2, val=5:  stack=[0,1]      → 8>5, pop 1→result[1]=5
                               → 4<5, no pop, push 2   stack=[0,2]
i=3, val=2:  stack=[0,2]      → 5>2, pop 2→result[2]=2
                               → 4>2, pop 0→result[0]=2
                               → push 3                stack=[3]
i=4, val=10: stack=[3]        → 2<10, no pop, push 4  stack=[3,4]
i=5, val=3:  stack=[3,4]      → 10>3, pop 4→result[4]=3
                               → 2<3, no pop, push 5   stack=[3,5]

Remaining in stack: indices 3,5 → result stays -1

Result: [2, 5, 2, -1, 3, -1] ✓

Previous Smaller Element (Left Side)

A common variant: for each element find the nearest smaller element to its left.

def prev_smaller_element(arr):
    """Nearest smaller element to the LEFT of each position."""
    n = len(arr)
    result = [-1] * n
    stack = []  # monotonic increasing stack of values

    for i in range(n):
        while stack and stack[-1] >= arr[i]:
            stack.pop()
        if stack:
            result[i] = stack[-1]
        stack.append(arr[i])

    return result

# Example:
# Input:  [4, 8, 5, 2, 10, 3]
# Output: [-1, 4, 4, -1, 2, 2]

Combining Both Sides

Many problems need both the previous smaller and next smaller for each element (e.g., Sum of Subarray Minimums, Largest Rectangle in Histogram).

def both_smaller(arr):
    """Get previous smaller and next smaller in one pass each."""
    n = len(arr)
    prev_smaller = [-1] * n
    next_smaller = [-1] * n

    # Previous smaller (left to right)
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        if stack:
            prev_smaller[i] = stack[-1]
        stack.append(i)

    # Next smaller (left to right)
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            idx = stack.pop()
            next_smaller[idx] = i
        stack.append(i)

    return prev_smaller, next_smaller

Edge Cases

1. All elements equal — [5, 5, 5] → [-1, -1, -1] (no strictly smaller)
2. Sorted ascending — [1, 2, 3] → [-1, -1, -1] (nothing smaller to the right)
3. Sorted descending — [3, 2, 1] → [2, 1, -1]
4. Single element — [7] → [-1]
5. Duplicates — watch > vs >= depending on strict or non-strict

Complexity Analysis

Approach	Time	Space
Brute force	O(n^2)	O(n)
Monotonic stack	O(n)	O(n)

Each element is pushed once and popped at most once, giving amortized O(1) per element.

When to Use This Pattern

Use Next Smaller Element (monotonic increasing stack) when you see:

• “Find the first smaller value to the right/left”
• Stock price problems asking for drops
• Histogram or bar-chart area problems
• Any problem combining previous-smaller + next-smaller boundaries
• Temperature problems looking for cooler days

Related Problems

Problem	Difficulty	Key Idea
LeetCode 496 — Next Greater Element I	Easy	Decreasing stack baseline
LeetCode 84 — Largest Rectangle in Histogram	Hard	Prev + next smaller bounds
LeetCode 907 — Sum of Subarray Minimums	Medium	Contribution with both sides
LeetCode 739 — Daily Temperatures	Medium	Next greater variant

Key Takeaway

The Next Smaller Element pattern is the complement of Next Greater. Swap the stack invariant from decreasing to increasing, and flip the comparison. Once you are comfortable with both, you can solve almost any monotonic-stack problem by recognizing which variant applies.