Monotonic Stack: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Monotonic Stack: Complete Guide with Examples

Welcome to the practice problems for the monotonic stack. If you need a refresher on the code, the code templates have the pattern in all 6 languages.

Note on the classic set: Largest Rectangle in Histogram and Trapping Rain Water already have full multi-language walkthroughs on the stack pattern problems page . This page skips duplicating those two and instead covers problems that no other pattern page owns.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

Next Greater Element I teaches the push and pop mechanism with a map layered on top.
Next Greater Element II adds the circular wrap simulated by a double pass over the array.
Online Stock Span swaps values for (price, span) pairs, which is how the same idea becomes a design problem.
Sum of Subarray Minimums needs previous and next boundaries at the same time, a real step up in detail.
Remove K Digits converts the pattern into a greedy sequence builder and forces you to think about ties.
Car Fleet sorts first, then collapses cars into fleets with a stack of arrival times.
132 Pattern reverses the scan direction, which makes it the trickiest of the medium set.
Maximal Rectangle extends the histogram helper to two dimensions, the classic hard capstone.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Next Greater Element I

LeetCode 496 | Difficulty: Easy

Brief: For every value in nums1, find its next greater element as that value appears inside nums2.

Why this pattern: The question is the exact definition of the pattern. The only extra is that the answer belongs to a subset of the input.

Key Insight: Run the monotonic stack once over nums2 and store every result in a map. Looking up an element of nums1 then costs constant time.

Visual:

    graph TD
    A["nums2: 1, 3, 4, 2"] --> B["3 pops 1, map[1] = 3"]
    B --> C["4 pops 3, map[3] = 4"]
    C --> D["4 and 2 get no greater value, map = -1"]
    D --> E["nums1 = 4, 1, 2 -> answer -1, 3, -1"]

Code:

var nextGreaterElement = function(nums1, nums2) {
    const map = new Map(); // value -> next greater element
    const stack = [];

    for (const num of nums2) {
        // Any waiting value smaller than num has found its answer.
        while (stack.length > 0 && stack[stack.length - 1] < num) {
            map.set(stack.pop(), num);
        }
        stack.push(num);
    }

    return nums1.map(n => map.has(n) ? map.get(n) : -1);
};

from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        mapping = {}
        stack = []

        for num in nums2:
            while stack and stack[-1] < num:
                mapping[stack.pop()] = num
            stack.append(num)

        return [mapping.get(n, -1) for n in nums1]

import java.util.*;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();

        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        return res;
    }
}

#include <vector>
#include <stack>
#include <unordered_map>

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map;
        stack<int> st;

        for (int num : nums2) {
            while (!st.empty() && st.top() < num) {
                map[st.top()] = num;
                st.pop();
            }
            st.push(num);
        }

        vector<int> res;
        for (int num : nums1) {
            res.push_back(map.count(num) ? map[num] : -1);
        }
        return res;
    }
};

func nextGreaterElement(nums1, nums2 []int) []int {
    mp := make(map[int]int)
    stack := []int{}

    for _, num := range nums2 {
        for len(stack) > 0 && stack[len(stack)-1] < num {
            mp[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, num)
    }

    res := make([]int, len(nums1))
    for i, num := range nums1 {
        if val, ok := mp[num]; ok {
            res[i] = val
        } else {
            res[i] = -1
        }
    }
    return res
}

def next_greater_element(nums1, nums2)
    mapping = {}
    stack = []

    nums2.each do |num|
        while !stack.empty? && stack.last < num
            mapping[stack.pop] = num
        end
        stack.push(num)
    end

    nums1.map { |n| mapping.fetch(n, -1) }
end

Here the stack stores values instead of indices. That works because the requested answer is a value, and the map turns one pass into constant-time lookups for nums1.

Medium Problems

2. Next Greater Element II

LeetCode 503 | Difficulty: Medium

Brief: Find the next greater element for every index in a circular array.

Why this pattern: This is the base problem with one extra condition. The circle means a second lap over the same indices is required.

Key Insight: Iterate 2 * n positions using modulo, and push an index onto the stack only during the first lap so it resolves at most once.

Visual:

    graph TD
    A["circle: 1, 2, 1"] --> B["index 0: next greater 2"]
    B --> C["index 1: no greater anywhere, -1"]
    C --> D["index 2: wraps to index 1, next greater 2"]
    D --> E["answer: 2, -1, 2"]

Code:

var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack = [];

    // Two laps simulate the circle so elements at the end
    // can still find an answer among elements at the start.
    for (let i = 0; i < 2 * n; i++) {
        const num = nums[i % n];
        while (stack.length > 0 && nums[stack[stack.length - 1]] < num) {
            res[stack.pop()] = num;
        }
        if (i < n) {
            stack.push(i);
        }
    }
    return res;
};

import java.util.*;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                res[stack.pop()] = num;
            }
            if (i < n) {
                stack.push(i);
            }
        }
        return res;
    }
}

#include <vector>
#include <stack>

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> st;

        for (int i = 0; i < 2 * n; ++i) {
            int num = nums[i % n];
            while (!st.empty() && nums[st.top()] < num) {
                res[st.top()] = num;
                st.pop();
            }
            if (i < n) {
                st.push(i);
            }
        }
        return res;
    }
};

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }
    stack := []int{}

    for i := 0; i < 2*n; i++ {
        num := nums[i%n]
        for len(stack) > 0 && nums[stack[len(stack)-1]] < num {
            res[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1]
        }
        if i < n {
            stack = append(stack, i)
        }
    }
    return res
}

The double lap is the crux. Everything unresolved after the first pass gets a second chance once the modulo wraps the scan back to the beginning. The maximum value of the array stays -1 because nothing can ever beat it.

3. Online Stock Span

LeetCode 901 | Difficulty: Medium

Brief: Design a class where next(price) returns the number of consecutive past days whose price was lower than or equal to today’s price.

Why this pattern: The span counts back until the previous larger price, which is a previous greater element measured in distance. A stack of (price, span) pairs keeps the whole history compressed.

Key Insight: When a new price pops a pair, fold that pair’s span into the new span. Popped pairs represent entire runs of days, so the history is never rescanned.

Visual:

    graph TD
    A["prices: 100, 80, 60, 70, 60, 75, 85"] --> B["70 pops 60, span of 70 = 2"]
    B --> C["75 pops 70 (span 2) and 60 (span 1), span = 4"]
    C --> D["85 pops 75 (span 4) and 60 (span 1), span = 6"]
    D --> E["spans: 1, 1, 1, 2, 1, 4, 6"]

Code:

var StockSpanner = function() {
    this.stack = []; // pairs [price, span]
};

StockSpanner.prototype.next = function(price) {
    let span = 1;
    // Each popped pair stands for its whole run of days,
    // so the current span grows by more than one at a time.
    while (this.stack.length > 0 && this.stack[this.stack.length - 1][0] <= price) {
        span += this.stack.pop()[1];
    }
    this.stack.push([price, span]);
    return span;
};

class StockSpanner:
    def __init__(self):
        self.stack = []  # pairs (price, span)

    def next(self, price: int) -> int:
        span = 1
        # Equal prices count toward the span, hence <= .
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

import java.util.*;

class StockSpanner {
    private Deque<int[]> stack; // [price, span]

    public StockSpanner() {
        stack = new ArrayDeque<>();
    }

    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{price, span});
        return span;
    }
}

#include <stack>

class StockSpanner {
    stack<pair<int, int>> st; // (price, span)
public:
    int next(int price) {
        int span = 1;
        while (!st.empty() && st.top().first <= price) {
            span += st.top().second;
            st.pop();
        }
        st.push({price, span});
        return span;
    }
};

type StockSpanner struct {
    stack [][2]int // [price, span]
}

func Constructor() StockSpanner {
    return StockSpanner{stack: make([][2]int, 0)}
}

func (this *StockSpanner) Next(price int) int {
    span := 1
    for len(this.stack) > 0 && this.stack[len(this.stack)-1][0] <= price {
        span += this.stack[len(this.stack)-1][1]
        this.stack = this.stack[:len(this.stack)-1]
    }
    this.stack = append(this.stack, [2]int{price, span})
    return span
}

class StockSpanner
    def initialize
        @stack = [] # [price, span]
    end

    def next(price)
        span = 1
        while !@stack.empty? && @stack.last[0] <= price
            span += @stack.pop[1]
        end
        @stack.push([price, span])
        span
    end
end

The combinatorial trick is folding spans. A long run of smaller days collapses into one pair, so the whole history is never visited again. The <= comparison matters: the definition of span includes equal prices.

4. Sum of Subarray Minimums

LeetCode 907 | Difficulty: Medium

Brief: Sum the minimum of every contiguous subarray.

Why this pattern: For each element, the stretch of subarrays where it is the minimum is bounded by the nearest strictly smaller element on the left and the nearest smaller-or-equal on the right. Both bounds are monotonic stack passes.

Key Insight: The number of subarrays where arr[i] is the minimum equals (i - prev_smaller) * (next_smaller_or_equal - i). Using a smaller-or-equal on only one side prevents double counting across duplicates.

Visual:

    graph TD
    A["arr: 3, 1, 2, 4"] --> B["3: prev -1, next 1 -> 1 x 1 = 1"]
    B --> C["1: prev -1, next 4 -> 2 x 3 = 6"]
    C --> D["2: prev 1, next 4 -> 1 x 2 = 2"]
    D --> E["4: prev 1, next 4 -> 1 x 1 = 1"]
    E --> F["total 3 + 6 + 4 + 4 = 17"]

Code:

var sumSubarrayMins = function(arr) {
    const MOD = 1e9 + 7;
    const n = arr.length;

    // prev[i]: nearest strictly smaller index on the left.
    const prev = new Array(n).fill(-1);
    let stack = [];
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        prev[i] = stack.length > 0 ? stack[stack.length - 1] : -1;
        stack.push(i);
    }

    // next[i]: nearest smaller-or-equal index on the right.
    // The equal side decides that each subarray is credited once.
    const next = new Array(n).fill(n);
    stack = [];
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        next[i] = stack.length > 0 ? stack[stack.length - 1] : n;
        stack.push(i);
    }

    let total = 0;
    for (let i = 0; i < n; i++) {
        total = (total + arr[i] * (i - prev[i]) * (next[i] - i)) % MOD;
    }
    return total;
};

from typing import List

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)

        # Nearest strictly smaller index on the left.
        prev = [-1] * n
        stack = []
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)

        # Nearest smaller-or-equal index on the right.
        next_ = [n] * n
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            next_[i] = stack[-1] if stack else n
            stack.append(i)

        total = 0
        for i in range(n):
            total = (total + arr[i] * (i - prev[i]) * (next_[i] - i)) % mod
        return total

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1_000_000_007;
        int n = arr.length;

        int[] prev = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            prev[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        int[] next = new int[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            next[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long total = 0;
        for (int i = 0; i < n; i++) {
            total = (total + (long) arr[i] * (i - prev[i]) * (next[i] - i)) % MOD;
        }
        return (int) total;
    }
}

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const long long MOD = 1e9 + 7;
        int n = arr.size();

        vector<int> prev(n), next(n);
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
            prev[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        while (!st.empty()) st.pop();

        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.top()] > arr[i]) st.pop();
            next[i] = st.empty() ? n : st.top();
            st.push(i);
        }

        long long total = 0;
        for (int i = 0; i < n; ++i) {
            total = (total + (long long) arr[i] * (i - prev[i]) * (next[i] - i)) % MOD;
        }
        return (int) total;
    }
};

func sumSubarrayMins(arr []int) int {
    const mod = 1_000_000_007
    n := len(arr)

    prev := make([]int, n)
    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && arr[stack[len(stack)-1]] >= arr[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            prev[i] = -1
        } else {
            prev[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    next := make([]int, n)
    stack = []int{}
    for i := n - 1; i >= 0; i-- {
        for len(stack) > 0 && arr[stack[len(stack)-1]] > arr[i] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            next[i] = n
        } else {
            next[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    total := 0
    for i := 0; i < n; i++ {
        left := i - prev[i]
        right := next[i] - i
        total = (total + (arr[i]*left*right)%mod) % mod
    }
    return total
}

def sum_subarray_mins(arr)
    mod = 10**9 + 7
    n = arr.length

    prev = Array.new(n)
    stack = []
    (0...n).each do |i|
        stack.pop while !stack.empty? && arr[stack.last] >= arr[i]
        prev[i] = stack.empty? ? -1 : stack.last
        stack.push(i)
    end

    next_ = Array.new(n)
    stack = []
    (n - 1).downto(0) do |i|
        stack.pop while !stack.empty? && arr[stack.last] > arr[i]
        next_[i] = stack.empty? ? n : stack.last
        stack.push(i)
    end

    total = 0
    (0...n).each do |i|
        total = (total + arr[i] * (i - prev[i]) * (next_[i] - i)) % mod
    end

    total
end

This solution runs two passes of the same stack, flipped only by direction. The contribution math depends on the equal policy on the right. Java and C++ need long for the products, because the multiplication can exceed a 32-bit int before the modulo happens.

5. Remove K Digits

LeetCode 402 | Difficulty: Medium

Brief: Remove k digits from the string num so the remaining digits form the smallest possible number.

Why this pattern: The smallest number keeps digits as small as possible from left to right, and a smaller digit can immediately replace a larger one sitting right before it. That replacement is a monotonic stack pop under a removal budget.

Key Insight: While a smaller digit arrives and budget remains, pop the larger digit on top. After the scan, any leftover budget is spent on the tail.

Visual:

    graph TD
    A["1432219, k = 3"] --> B["4 is removed when 3 arrives"]
    B --> C["3 is removed when 2 arrives"]
    C --> D["2 is removed when 1 arrives"]
    D --> E["result: 1219"]

Code:

var removeKdigits = function(num, k) {
    const stack = [];
    for (const digit of num) {
        // A smaller digit makes the larger one in front
        // useless for a minimal number, so remove it.
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }
    // An increasing tail needs no more removals, but the
    // budget still gets spent, and removing from the end
    // keeps the number smallest.
    while (k > 0) {
        stack.pop();
        k--;
    }
    return stack.join('').replace(/^0+/, '') || '0';
};

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for digit in num:
            while k > 0 and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)

        if k > 0:
            stack = stack[:-k]

        result = ''.join(stack).lstrip('0')
        return result or '0'

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder stack = new StringBuilder();
        for (int i = 0; i < num.length(); i++) {
            char digit = num.charAt(i);
            while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > digit) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            stack.append(digit);
        }
        while (k > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }
        while (stack.length() > 0 && stack.charAt(0) == '0') {
            stack.deleteCharAt(0);
        }
        return stack.length() == 0 ? "0" : stack.toString();
    }
}

class Solution {
public:
    string removeKdigits(string num, int k) {
        string stack;
        for (char digit : num) {
            while (k > 0 && !stack.empty() && stack.back() > digit) {
                stack.pop_back();
                k--;
            }
            stack.push_back(digit);
        }
        while (k > 0) {
            stack.pop_back();
            k--;
        }
        size_t start = stack.find_first_not_of('0');
        return start == string::npos ? "0" : stack.substr(start);
    }
};

import "strings"

func removeKdigits(num string, k int) string {
    stack := []byte{}
    for i := 0; i < len(num); i++ {
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
            stack = stack[:len(stack)-1]
            k--
        }
        stack = append(stack, num[i])
    }
    stack = stack[:len(stack)-k]

    result := strings.TrimLeft(string(stack), "0")
    if result == "" {
        return "0"
    }
    return result
}

def remove_kdigits(num, k)
    stack = []

    num.each_char do |digit|
        while k > 0 && !stack.empty? && stack.last > digit
            stack.pop
            k -= 1
        end
        stack.push(digit)
    end

    stack = stack[0...-k] if k > 0

    result = stack.join.sub(/^0+/, '')
    result.empty? ? '0' : result
end

The greedy step is the pop. When a smaller digit arrives and budget remains, the larger digit on top must go, because keeping it makes the number bigger. After the scan the tail is increasing, so removals there do the least damage; leading zeros are then stripped from the result.

6. Car Fleet

LeetCode 853 | Difficulty: Medium

Brief: Count the fleets that arrive at the target, given each car’s position and speed.

Why this pattern: A car behind only becomes a new fleet if it arrives later than the fleet in front. Sorting by position descending, then collapsing cars that catch up, is the monotonic stack idea applied to arrival times.

Key Insight: Compute the time each car needs to reach the target. While scanning from the closest car to the farthest, a time not larger than the recorded leader merges into that fleet.

Visual:

    graph TD
    A["target 12: (10,2) (8,1) (5,1) (3,3) (0,1)"] --> B["reach times: 1, 4, 7, 3, 12"]
    B --> C["sorted by position: 1, 4, 7, 3, 12"]
    C --> D["stack keeps only larger times: 1, 4, 7, 12"]
    D --> E["3 fleets"]

Code:

var carFleet = function(target, position, speed) {
    const cars = position
        .map((pos, i) => [pos, speed[i]]) // [position, speed]
        .sort((a, b) => b[0] - a[0]);     // farthest first
    const stack = []; // arrival times of leading fleets

    for (const [pos, sp] of cars) {
        const time = (target - pos) / sp;
        // If this car needs no more time than the leader,
        // it is absorbed by the fleet running ahead.
        if (stack.length === 0 || time > stack[stack.length - 1]) {
            stack.push(time);
        }
    }
    return stack.length;
};

from typing import List

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        cars = sorted(zip(position, speed), reverse=True)  # farthest first
        stack = []  # arrival times of fleet leaders

        for pos, sp in cars:
            arrival = (target - pos) / sp
            if not stack or arrival > stack[-1]:
                stack.append(arrival)
        return len(stack)

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> position[b] - position[a]); // farthest first

        Deque<Double> stack = new ArrayDeque<>();
        for (int idx : order) {
            double arrival = (double) (target - position[idx]) / speed[idx];
            if (stack.isEmpty() || arrival > stack.peek()) {
                stack.push(arrival);
            }
        }
        return stack.size();
    }
}

#include <vector>
#include <algorithm>
#include <stack>

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        int n = position.size();
        vector<pair<int, int>> cars; // (position, speed)
        for (int i = 0; i < n; ++i) {
            cars.push_back({position[i], speed[i]});
        }
        sort(cars.rbegin(), cars.rend()); // farthest first

        stack<double> st; // arrival times of leading fleets
        for (auto [pos, sp] : cars) {
            double arrival = (target - pos) / (double) sp;
            if (st.empty() || arrival > st.top()) {
                st.push(arrival);
            }
        }
        return st.size();
    }
};

import "sort"

func carFleet(target int, position []int, speed []int) int {
    n := len(position)
    order := make([]int, n)
    for i := range order {
        order[i] = i
    }
    // Farthest car first.
    sort.Slice(order, func(a, b int) bool {
        return position[order[a]] > position[order[b]]
    })

    stack := []float64{} // arrival times of leading fleets
    for _, i := range order {
        arrival := float64(target-position[i]) / float64(speed[i])
        if len(stack) == 0 || arrival > stack[len(stack)-1] {
            stack = append(stack, arrival)
        }
    }
    return len(stack)
}

def car_fleet(target, position, speed)
    cars = position.zip(speed).sort_by { |pos, _| -pos } # farthest first
    stack = [] # arrival times of leading fleets

    cars.each do |pos, sp|
        arrival = (target - pos).to_f / sp
        stack.push(arrival) if stack.empty? || arrival > stack.last
    end

    stack.length
end

The ordering step matters. By handling the farthest car first, each farther car only ever compares against the fleet ahead of it. A car with equal arrival time merges with that fleet, so the total count is the number of strictly increasing arrival records.

7. 132 Pattern

LeetCode 456 | Difficulty: Medium

Brief: Return true if there exist three indices i < j < k such that nums[i] < nums[k] < nums[j].

Why this pattern: The pattern needs a candidate “3” with the largest possible “2” behind it. A stack of candidates keeps those values while scanning right to left.

Key Insight: Track third, the largest value that has been popped so far. When scanning from right to left, any nums[i] < third completes the triple, because the popped value sits to the right of nums[j] and is smaller than nums[j].

Visual:

    graph TD
    A["nums: 3, 1, 4, 2"] --> B["scan right: 2, then 4"]
    B --> C["4 pops 2, third = 2"]
    C --> D["1 < third(2)? yes"]
    D --> E["return true"]

Code:

var find132pattern = function(nums) {
    const stack = [];   // candidates for the "3"
    let third = -Infinity; // best "2" seen so far

    for (let i = nums.length - 1; i >= 0; i--) {
        // Anything smaller than the best "2" found can be the "1".
        if (nums[i] < third) return true;
        // Smaller values popped now can serve as "2" for
        // an even earlier "1", keep the largest of them.
        while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
            third = stack.pop();
        }
        stack.push(nums[i]);
    }
    return false;
};

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []  # candidates for the "3"
        third = float("-inf")  # best "2" value seen so far

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] < third:
                return True
            while stack and stack[-1] < nums[i]:
                third = stack.pop()
            stack.append(nums[i])

        return False

class Solution {
    public boolean find132pattern(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int third = Integer.MIN_VALUE; // best "2" value seen so far

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < third) return true;
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                third = stack.pop();
            }
            stack.push(nums[i]);
        }
        return false;
    }
}

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> st;
        int third = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; --i) {
            if (nums[i] < third) return true;
            while (!st.empty() && st.top() < nums[i]) {
                third = st.top();
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};

import "math"

func find132pattern(nums []int) bool {
    var stack []int
    third := math.MinInt32 // best "2" value seen so far

    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] < third {
            return true
        }
        for len(stack) > 0 && stack[len(stack)-1] < nums[i] {
            third = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, nums[i])
    }
    return false
}

def find132pattern(nums)
    stack = []           # candidates for the "3"
    third = -Float::INFINITY # best "2" seen so far

    (nums.length - 1).downto(0) do |i|
        return true if nums[i] < third
        while !stack.empty? && stack.last < nums[i]
            third = stack.pop
        end
        stack.push(nums[i])
    end

    false
end

The right-to-left pass is the point of the problem. Values that get popped while a taller “3” arrives are exactly the best “2” candidates, because they are both smaller than the “3” and located to its right. Keeping the largest popped value maximizes the chance that an earlier element qualifies as the “1”.

Hard Problems

8. Maximal Rectangle

LeetCode 85 | Difficulty: Hard

Brief: Find the largest rectangle of 1s inside a binary matrix.

Why this pattern: Each row can be turned into a histogram of consecutive ones. The largest-rectangle solver from problem 4 then runs against every row, and the best result across all rows is the answer.

Key Insight: For each cell, add 1 to the column height when the cell is '1', else reset it to 0. Then the histogram helper computes the widest rectangle for that row. The classic duplication of Largest Rectangle in Histogram is avoided by reusing this helper.

Visual:

    graph TD
    A["row 1: 1 0 1 0 0 -> heights 1 0 1 0 0"] --> B["row 2: 1 0 1 1 1 -> heights 2 0 2 1 1"]
    B --> C["row 3: 1 1 1 1 1 -> heights 3 1 3 2 2"]
    C --> D["histogram area for row 3: 6"]
    D --> E["answer: 6"]

Code:

var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (const row of matrix) {
        // Build the histogram for this row from the
        // vertical run of consecutive ones in each column.
        for (let j = 0; j < cols; j++) {
            heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
        }
        maxArea = Math.max(maxArea, largestRectangleArea(heights.slice()));
    }
    return maxArea;
};

function largestRectangleArea(heights) {
    heights.push(0); // sentinel flushes the remaining bars
    const stack = [];
    let maxArea = 0;

    for (let i = 0; i < heights.length; i++) {
        // The top bar's right boundary is the current index.
        while (stack.length > 0 && heights[i] < heights[stack[stack.length - 1]]) {
            const h = heights[stack.pop()];
            const w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }
    return maxArea;
}

from typing import List

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        cols = len(matrix[0])
        heights = [0] * cols
        max_area = 0

        for row in matrix:
            for j in range(cols):
                heights[j] = heights[j] + 1 if row[j] == '1' else 0
            max_area = max(max_area, self.largestRectangleArea(heights[:]))

        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)  # sentinel flushes the remaining bars
        stack = []
        max_area = 0

        for i, h in enumerate(heights):
            while stack and h < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        return max_area

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;

        int cols = matrix[0].length;
        int[] heights = new int[cols];
        int maxArea = 0;

        for (char[] row : matrix) {
            for (int j = 0; j < cols; j++) {
                heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights.clone()));
        }
        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            // A virtual zero at index n forces the final flush.
            int h = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int cols = matrix[0].size();
        vector<int> heights(cols, 0);
        int maxArea = 0;

        for (const auto& row : matrix) {
            for (int j = 0; j < cols; ++j) {
                heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

private:
    int largestRectangleArea(vector<int> heights) {
        heights.push_back(0); // sentinel flushes the remaining bars
        stack<int> st;
        int maxArea = 0;
        for (int i = 0; i < (int) heights.size(); ++i) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            st.push(i);
        }
        return maxArea;
    }
};

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    cols := len(matrix[0])
    heights := make([]int, cols)
    maxArea := 0

    for _, row := range matrix {
        for j := 0; j < cols; j++ {
            if row[j] == '1' {
                heights[j]++
            } else {
                heights[j] = 0
            }
        }
        area := largestRectangleArea(append([]int{}, heights...))
        if area > maxArea {
            maxArea = area
        }
    }
    return maxArea
}

func largestRectangleArea(heights []int) int {
    heights = append(heights, 0) // sentinel flushes remaining bars
    var stack []int
    maxArea := 0

    for i, h := range heights {
        for len(stack) > 0 && h < heights[stack[len(stack)-1]] {
            height := heights[stack[len(stack)-1]]
            stack = stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            if area := height * width; area > maxArea {
                maxArea = area
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

def maximal_rectangle(matrix)
    return 0 if matrix.empty?

    cols = matrix[0].length
    heights = Array.new(cols, 0)
    max_area = 0

    matrix.each do |row|
        (0...cols).each do |j|
            heights[j] = row[j] == '1' ? heights[j] + 1 : 0
        end
        max_area = [max_area, largest_rectangle_area(heights.dup)].max
    end

    max_area
end

def largest_rectangle_area(heights)
    heights << 0
    stack = []
    max_area = 0

    heights.each_with_index do |h, i|
        while !stack.empty? && h < heights[stack.last]
            height = heights[stack.pop]
            width = stack.empty? ? i : i - stack.last - 1
            max_area = [max_area, height * width].max
        end
        stack.push(i)
    end

    max_area
end

The helper is the whole strongest point of this problem. Turn each row into a histogram, then run the helper over the heights. The sentinel zero at the end forces the remaining bars on the stack to flush without a separate cleanup loop.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These eight problems cover the pattern end to end. Start from the one-pass next greater mechanic, add circular wrapping, distance and pair tricks, then the two-boundary reasoning, and finish with the histogram capstone. If you want more, remember that Largest Rectangle in Histogram and Trapping Rain Water have full solutions on the stack problems page , and they are the standard next stop after this set.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .