Stack Patterns

Previous Smaller Element

Problem: Find the index of first smaller element to the LEFT.

Input: [2, 1, 5, 6, 2, 3]
Target Output: [-1, -1, 1, 2, 1, 4]

Reasoning:

Index 0 (2): Nothing to left. → -1
Index 1 (1): 2 is not smaller. Nothing else. → -1
Index 2 (5): Left is 1. 1 < 5. → 1
Index 3 (6): Left is 5. 5 < 6. → 2
Index 4 (2): Left is 6 (no), 5 (no), 1 (yes). → 1

Implementation

def previous_smaller_element_indices(heights: list[int]) -> list[int]:
    n = len(heights)
    result = [-1] * n
    stack = []
 
    for i in range(n):
        current_height = heights[i]
 
        while stack and heights[stack[-1]] >= current_height:
            stack.pop()
 
        if stack:
            result[i] = stack[-1]
 
        stack.append(i)
 
    return result

fn previous_smaller_element_indices(heights: Vec<i32>) -> Vec<i32> {
    let mut stack: Vec<usize> = Vec::new();
    let len = heights.len();
    let mut result: Vec<i32> = vec![-1; len];
 
    for (i, item) in heights.iter().enumerate() {
        while !stack.is_empty() && heights[*stack.last().unwrap()] >= *item {
            stack.pop();
        }
 
        if !stack.is_empty() {
            result[i] = *stack.last().unwrap() as i32;
        }
 
        stack.push(i);
    }
    result
}
 
fn main() {
    let h = vec![2, 1, 5, 6, 2, 3];
    let res = previous_smaller_element_indices(h);
    println!("{:?}", res); // Output: [-1, -1, 1, 2, 1, 4]
}

Daily Temperatures

Problem: Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0.

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

Logic:

Is this “Next Greater” or “Next Smaller”? → Next Greater.
Therefore: Monotonic Decreasing Stack.
Difference: We don’t store the index of the next greater element; we store the difference between indices (found_index - current_index).
We will push all the temperature indexes if the current_index is less than prev_index.
If not then we will store the different between prev_index and current_index at result[prev_index] telling that’s the next warmer temperature for the prev_index.

Complexity

Time Complexity: O(N)
- Each element is added to the stack exactly once.
- Each element is removed from the stack at most once.
- Therefore, the operations are linear.
Space Complexity: O(N)
- (Worst case: decreasing array like [50, 40, 30], stack fills up).

Implementation

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    stack = []
    result = [0] * len(temperatures)
 
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            result[stack[-1]] = i - stack[-1]
            stack.pop()
 
        stack.append(i)
 
    return result

pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let mut stack: Vec<usize> = Vec::new();
    let n: usize = temperatures.len();
    let mut result: Vec<i32> = vec![0; n];
 
    for (i, t) in temperatures.iter().enumerate() {
        while !stack.is_empty() && temperatures[*stack.last().unwrap()] < *t {
            result[*stack.last().unwrap()] = (i - *stack.last().unwrap()) as i32;
            stack.pop();
        }
        stack.push(i);
    }
    result
}
 
fn main() {}

Largest Rectangle Area

Given heights of bars, find the area of the largest rectangle that fits. Example: [2, 1, 5, 6, 2, 3]

Method 1: Two-Pass

For every single bar, we ask two questions:

Look Left: Who is the first person smaller than me? That index is my Left Limit.
Look Right: Who is the first person smaller than me? That index is my Right Limit.

Once we know the limits, the width is simple: $Width = (Right Limit - Left Limit) - 1$

Visual Trace

Focus on the bar at Index 2 (Height 5).

Look Left: Index 1 has height 1. 1 < 5. So Left Limit = 1.
Look Right: Index 3 is 6 (taller). Keep looking. Index 4 is 2 (smaller). Stop. Right Limit = 4.
Calculation:
- Width: $4 - 1 - 1 = 2$ .
- Area: $5 \times 2 = 10$ .

Implementation

def largest_rectangle_two_pass(heights: list[int]) -> int:
    n = len(heights)
    left_limits = [-1] * n
    right_limits = [n] * n  # Default is N (end of array)
 
    # Pass 1: Find Previous Smaller (Left Limit)
    stack = []  # Stores INDICES
    for i in range(n):
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            left_limits[i] = stack[-1]
        stack.append(i)
 
    # Pass 2: Find Next Smaller (Right Limit)
    stack = []
    for i in range(n - 1, -1, -1):  # Loop backwards
        while stack and heights[stack[-1]] >= heights[i]:
            stack.pop()
        if stack:
            right_limits[i] = stack[-1]
        stack.append(i)
 
    # Final Pass: Calculate Area
    max_area = 0
    for i in range(n):
        width = right_limits[i] - left_limits[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)
 
    return max_area

use std::cmp::max;
 
pub fn largest_rectangle_two_pass(heights: Vec<i32>) -> i32 {
    let n = heights.len();
    let mut left_limits = vec![-1; n];
    let mut right_limits = vec![n as i32; n]; // Default to n
 
    // Pass 1: Left Limits
    let mut stack: Vec<usize> = Vec::new();
    for i in 0..n {
        while !stack.is_empty() && heights[*stack.last().unwrap()] >= heights[i] {
            stack.pop();
        }
        if !stack.is_empty() {
            left_limits[i] = *stack.last().unwrap() as i32;
        }
        stack.push(i);
    }
 
    // Pass 2: Right Limits
    stack.clear();
    for i in (0..n).rev() {
        // Loop backwards
        while !stack.is_empty() && heights[*stack.last().unwrap()] >= heights[i] {
            stack.pop();
        }
        if !stack.is_empty() {
            right_limits[i] = *stack.last().unwrap() as i32;
        }
        stack.push(i);
    }
 
    // Calculate Max Area
    let mut max_area = 0;
    for i in 0..n {
        let width = right_limits[i] - left_limits[i] - 1;
        max_area = max(max_area, heights[i] * width);
    }
    max_area
}

Method 2: One-Pass

We iterate through the array once. We maintain a stack of increasing heights.

When we see a taller bar, we just push it. It might be the start of a huge rectangle.
When we see a smaller bar (say at index i), it means the taller bars in the stack cannot extend any further right. The party is over for them.
The Trigger: The current smaller bar i is the Right Limit for the bars we pop. The Left Limit is simply the new top of the stack.

Visual Trace

Stack: [Index 1 (Val 1), Index 2 (Val 5), Index 3 (Val 6)] Current i = 4. Value = 2.

Compare 2 vs Top (6). 2 < 6. Pop 6.
- Height: 6.
- Right Edge: 4 (The current index i).
- Left Edge: 2 (The new stack top, Index 2).
- Width: 4 - 2 - 1 = 1. Area: 6.
Compare 2 vs Top (5). 2 < 5. Pop 5.
- Height: 5.
- Right Edge: 4.
- Left Edge: 1 (The new stack top, Index 1).
- Width: 4 - 1 - 1 = 2. Area: 10.

Implementation

def largest_rectangle_one_pass(heights: list[int]) -> int:
    # We add 0 at the end to force the stack to empty
    # This acts as a "Right Limit" for everything remaining
    heights.append(0)
    stack = []
    max_area = 0
 
    for i, current_h in enumerate(heights):
        # If current bar is smaller than stack top, calculate area for stack top
        while stack and heights[stack[-1]] >= current_h:
            h = heights[stack.pop()]
 
            # If stack is empty, it means h was the smallest so far.
            # It extends all the way from 0 to i.
            if not stack:
                width = i
            else:
                width = i - stack[-1] - 1
 
            max_area = max(max_area, h * width)
 
        stack.append(i)
 
    return max_area

use std::cmp::max;
 
pub fn largest_rectangle_one_pass(heights: Vec<i32>) -> i32 {
    let mut stack: Vec<usize> = Vec::new();
    let mut max_area = 0;
    let n = heights.len();
 
    // Loop 0..=n means we go one step PAST the end
    for i in 0..=n {
        // If we are at index n, treat height as 0 to force pops
        let current_h = if i == n { 0 } else { heights[i] };
 
        while !stack.is_empty() && heights[*stack.last().unwrap()] >= current_h {
            let h_index = stack.pop().unwrap();
            let height = heights[h_index];
 
            // Width Calculation Logic:
            let width = if stack.is_empty() {
                i as i32
            } else {
                (i - stack.last().unwrap() - 1) as i32
            };
 
            max_area = max(max_area, height * width);
        }
        stack.push(i);
    }
    max_area
}

Why?

If you tried to solve this intuitively without a stack, you would do this:

Pick bar $i$ .
Run a loop to the left to find where it stops.
Run a loop to the right to find where it stops.
Calculate area.

The Cost:

For every bar ( $N$ ), you scan the array ( $N$ ).
Total Complexity: $O (N^{2})$ .
With $N = 100, 000$ , $N^{2}$ is 10 billion operations. This will time out (TLE) in any coding interview.

The Stack Solution:

By using the Monotonic Stack, we find the boundaries in $O (1)$ average time per element.
Total Complexity: $O (N)$ .
This makes the code run instantly.

What?

Method	Time Complexity	Space Complexity	Pros	Cons
Brute Force	$O (N^{2})$	$O (1)$	Easy to write	Too slow for real data
Two-Pass	$O (N)$	$O (3 N)$	Easy to understand logic	Uses 3x memory (Left, Right, Stack arrays)
One-Pass	$O (N)$	$O (N)$	Maximum Efficiency	Logic is harder to visualize

How?

You generally won’t see “Histogram” in the problem title. You need to spot the structural pattern.

The Trigger: Use this specific Monotonic Stack logic when a problem involves “Expanding” an element until a condition is broken.

Checklist to Identify:

“Contiguous Subarray”: The problem asks for a continuous range (width of rectangle).
“Min/Max limit”: The range is determined by the minimum or maximum value inside it (the height of the rectangle is limited by the shortest bar).
“Nearest Smaller/Greater”: The boundary stops exactly when you hit a specific value (smaller than current).

My Wiki

Explorer

Stack Patterns

Previous Smaller Element

Implementation

Daily Temperatures

Complexity

Implementation

Largest Rectangle Area

Method 1: Two-Pass

Visual Trace

Implementation

Method 2: One-Pass

Visual Trace

Implementation

Why?

What?

How?

Table of Contents