INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER
01
00/15
01 / COVER MODULE 13 · MONOTONIC STACK & DEQUE
INVARIANT · MODULE 13 · MONOTONIC STACK & DEQUE
POP WHAT CAN NEVER WIN AGAIN

A value that a bigger one has passed can never be an answer again, so throw it away. What is left on the stack is sorted, without ever sorting. Each value is pushed once and popped once, and an O(n²) scan becomes O(n). Nine moves, fifteen problems.

15Problems
7Families
9Units
10Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

NEXT GREATER · 04
LOOKING BACK · 02
COLLISIONS AND FLEETS · 02
KEEP IT INCREASING · 01
EACH ELEMENT'S SHARE · 02
THE WIDEST RUN · 02
THE MONOTONIC DEQUE · 02
SOLVED HAS A JUDGE LINK
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
03 / MECHANISM UNIT 01 · WAITING FOR SOMETHING BIGGER

THE DAY THAT POPS YOU IS YOUR ANSWER

A day waits on the stack until a warmer day arrives. The warmer day pops it, and the gap i − j is its answer.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
04 / DRILL UNIT 01 · Waiting for Something Bigger · 1 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

nums2 = [2, 7, 3, 5, 4, 6, 8]. What is the next greater element of 3?

5 is the first value after 3 that is bigger. 3 waits on the stack until 5 pops it.

DRILL 02 · RECALL

When the scan ends, which values are still on the stack?

Nothing bigger came after them, so nothing popped them. Their answer is −1, or 0 days.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
05 / PROBLEM #01 · NEXT · EASY

Next Greater Element I

EASY next ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

For each value, the first greater value to its right. The queries come from a second array, so answer every value once and look the queries up.

INTUITION

Read nums2 once. A value waits on the stack until a bigger one arrives, and that arrival is its answer. Store the answers in a map.

STEPS
  1. Read x from nums2
  2. Pop every waiting value smaller than x, and record x as its answer
  3. Push x; it waits for something bigger
  4. Answer each query from the map, or −1
BRUTEO(n · m) scanning right from each query
→
OPTIMALO(n + m)
↕ SCROLL
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> nxt;            // value → its next greater
    vector<int> st;                          // values still waiting
    for (int x : nums2) {
        while (!st.empty() && st.back() < x) {
            nxt[st.back()] = x;              // x is the first bigger one
            st.pop_back();
        }
        st.push_back(x);
    }
    vector<int> ans;
    for (int x : nums1) ans.push_back(nxt.count(x) ? nxt[x] : -1);
    return ans;
}
TIMEO(n + m)each value pushed and popped at most once
SPACEO(n)the stack and the map
TRAP

Searching nums2 once per query. Finding x and scanning right from it is O(n · m). One pass over nums2 answers every value at once.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
06 / PROBLEM #02 · NEXT · MED

Daily Temperatures

MED next ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“How many days until a warmer one?” A distance to the next greater value, so the stack must hold indices, not temperatures.

INTUITION

A day waits on the stack until a warmer day pops it. The gap between the two indices is the answer. Days still waiting at the end keep 0.

STEPS
  1. Read day i
  2. While the day j on top is colder, pop it and set ans[j] = i − j
  3. Push i
  4. Whatever is left never warms up: 0
BRUTEO(n²) scanning ahead from every day
→
OPTIMALO(n)
↕ SCROLL
vector<int> dailyTemperatures(vector<int>& temperatures) {
    vector<int>& t = temperatures;
    int n = t.size();
    vector<int> ans(n, 0), st;               // st: days still waiting
    for (int i = 0; i < n; i++) {
        while (!st.empty() && t[st.back()] < t[i]) {
            ans[st.back()] = i - st.back();  // day i is the warmer one
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;                              // days left waiting keep 0
}
TIMEO(n)each day pushed once and popped at most once
SPACEO(n)the stack of waiting days
TRAP

Pushing the temperature. The answer is a distance, so the stack needs the day. With indices on the stack, t[st.back()] still gives the temperature.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
07 / DRILL UNIT 01 · Waiting for Something Bigger · 2 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

dailyTemperatures([30, 40, 50, 60])?

Each day is popped by the very next one. The last day is never popped, so it keeps 0.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
08 / PROBLEM #03 · NEXT · HARD

Number of Visible People in a Queue

HARD next ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Person i sees person j when everyone between them is shorter than both. Count, for each person, how many they see to the right.

INTUITION

Walk from the right. The people i could see are on a stack, taller toward the bottom. Each shorter one on top is seen by i and then hidden behind i, so pop it. The first taller one is seen too, and blocks the rest.

STEPS
  1. Walk i from right to left
  2. Pop every shorter person on top, counting each one
  3. If anyone is left, add 1 for the first taller person
  4. Push heights[i]
BRUTEO(n²) walking right from each person with a running maximum
→
OPTIMALO(n)
↕ SCROLL
vector<int> canSeePersonsCount(vector<int>& heights) {
    int n = heights.size();
    vector<int> ans(n), st;                  // heights to the right, taller below
    for (int i = n - 1; i >= 0; i--) {
        int seen = 0;
        while (!st.empty() && st.back() < heights[i]) {
            st.pop_back();                   // seen by i, then hidden by i
            seen++;
        }
        if (!st.empty()) seen++;             // the first person taller than i
        ans[i] = seen;
        st.push_back(heights[i]);
    }
    return ans;
}
TIMEO(n)each person pushed once and popped at most once
SPACEO(n)the stack
TRAP

Forgetting the one who blocks. The pops count the shorter people, and the first taller person is seen as well. Without the +1, every answer is one short except where nobody taller is left.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
09 / DRILL UNIT 01 · Waiting for Something Bigger · 3 OF 3

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

heights = [5, 1, 2, 3, 10]. How many people does the first one, of height 5, see?

Everyone between 5 and each of 1, 2, 3 and 10 is shorter than both. Nobody stands after 10.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
10 / MECHANISM UNIT 02 · AROUND THE CIRCLE

TWO LAPS, ONE PUSH EACH

Read nums[i % n] for i up to 2n − 1. The first lap pushes and answers; the second lap only answers.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
11 / DRILL UNIT 02 · Around the Circle

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

nextGreaterElements([5, 4, 3, 2, 1])?

Going round, every value meets the 5 at the start. Nothing is bigger than 5 itself.

DRILL 02 · RECALL

Why does the second lap not push?

Every index was pushed on the first lap. The second lap only lets the ones still waiting see the values before them.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
12 / PROBLEM #04 · NEXT · MED

Next Greater Element II

MED next ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The array is circular: after the last value, the search for a greater one goes on from the start.

INTUITION

Read the array twice, index i % n. The first lap pushes and answers; the second lap only answers, so no index waits twice.

STEPS
  1. Fill ans with −1
  2. For i in 0 … 2n − 1, read x = nums[i % n]
  3. Pop every waiting index whose value is smaller, and give it x
  4. Push i only while i < n
BRUTEO(n²) scanning up to n − 1 places round the circle
→
OPTIMALO(n)
↕ SCROLL
vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1), st;              // st: indices still waiting
    for (int i = 0; i < 2 * n; i++) {        // read the array twice
        int x = nums[i % n];
        while (!st.empty() && nums[st.back()] < x) {
            ans[st.back()] = x;
            st.pop_back();
        }
        if (i < n) st.push_back(i);          // only the first lap pushes
    }
    return ans;                              // never answered: still −1
}
TIMEO(n)2n reads; each index pushed once
SPACEO(n)the stack and ans
TRAP

One lap. A value near the end whose next greater is back at the start is never answered: [1, 2, 1] gives [2, −1, −1] instead of [2, −1, 2].

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
13 / MECHANISM UNIT 03 · LOOKING BACK

A POPPED DAY HANDS OVER ITS SPAN

Each entry is (price, span). Today absorbs every price on top that is at most its own, and their spans add up.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
14 / DRILL UNIT 03 · Looking Back · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

A StockSpanner gets 31, 41, 48, 59 and 79, in that order. What does the last call return?

Every price so far is at most 79. It absorbs (59, 4), so its span is 1 + 4.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
15 / PROBLEM #05 · BACK · MED

Online Stock Span

MED back ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Each call adds today's price and asks how many days in a row, ending today, the price was at most today's.

INTUITION

Keep (price, span) pairs, prices falling toward the top. Today absorbs every pair on top with a price at most its own, and adds up their spans.

STEPS
  1. span = 1, for today
  2. While the top price is ≤ price, add its span and pop it
  3. Push (price, span)
  4. Return span
BRUTEO(n) per call walking back through every price
→
OPTIMALO(1) amortised
↕ SCROLL
class StockSpanner {
    vector<pair<int, int>> st;               // (price, span), prices fall upward
public:
    StockSpanner() {}
    int next(int price) {
        int span = 1;                        // today
        while (!st.empty() && st.back().first <= price) {
            span += st.back().second;        // absorb its days
            st.pop_back();
        }
        st.push_back({price, span});
        return span;
    }
};
TIMEO(1) amortisedeach price pushed once and popped at most once
SPACEO(n)the stack of pairs
TRAP

Popping without keeping the span. A popped pair stands for every day it absorbed. Adding 1 per pop instead of its span undercounts as soon as two absorbs chain.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
16 / PROBLEM #06 · BACK · EASY

Nearest Smaller Values

EASY back ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

For every position, the nearest position to its left with a smaller value, or 0. Positions count from 1.

INTUITION

Scan left to right with a stack of positions whose values rise toward the top. Pop every value at least x[i]: it can never be the answer for i or anything after i. The top is then i's answer.

STEPS
  1. Read x[i]
  2. Pop while the top's value is ≥ x[i]
  3. Print the top's position (1-based), or 0 if the stack is empty
  4. Push i
BRUTEO(n²) scanning left from every position
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> x(n), st;                    // st: positions, values rising upward
    for (int& v : x) cin >> v;
    string out;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && x[st.back()] >= x[i]) st.pop_back();   // never again
        out += to_string(st.empty() ? 0 : st.back() + 1);           // 1-based, or 0
        out += i + 1 < n ? ' ' : '\n';
        st.push_back(i);
    }
    cout << out;
}
TIMEO(n)each position pushed once and popped at most once
SPACEO(n)the stack
TRAP

Popping only the larger values. An equal value is not smaller, so it is never an answer. Testing > instead of >= prints its position.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
17 / DRILL UNIT 03 · Looking Back · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Nearest Smaller Values on 3 1 4 1 5, with positions from 1?

The second 1 is not smaller than the first, so it gets 0. The 5 sees the 1 beside it.

DRILL 02 · BUG

A solution pops while x[top] > x[i]. What does it print on 2 2?

The first 2 stays on the stack, so the second prints position 1. But 2 is not smaller than 2; the answer is 0 0.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
18 / MECHANISM UNIT 04 · ASTEROID COLLISIONS

ONLY THE TOP SURVIVOR CAN BE HIT

A left-mover meets the newest right-mover first. It breaks smaller ones until it breaks, ties, or nothing is left to hit.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
19 / MECHANISM UNIT 04 · CAR FLEETS

A CAR THAT WOULD ARRIVE SOONER CATCHES UP

Sort closest first and work out when each car would arrive alone. No later than the fleet ahead: it joins. Later: a new fleet.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
20 / DRILL UNIT 04 · Collisions and Fleets · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

asteroidCollision([5, 10, −5])?

−5 meets 10 first, and 10 is bigger, so −5 breaks. It never reaches the 5.

DRILL 02 · TRACE

asteroidCollision([−2, −1, 1, 2])?

The left-movers are already on the left and the right-movers on the right. Nothing meets.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
21 / PROBLEM #07 · COLLIDE · MED

Asteroid Collision

MED collide ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Asteroids move at one speed; a sign gives the direction. A collision needs a right-mover on the left meeting a left-mover on the right.

INTUITION

The survivors so far are a stack. Only a left-mover can collide, and it meets the top survivor first. It keeps breaking smaller right-movers until it breaks, ties, or reaches a left-mover or nothing.

STEPS
  1. Read x; it is alive
  2. While x moves left and the top moves right, compare their sizes
  3. Smaller top: pop it, x flies on. Equal: pop it, x breaks. Bigger: x breaks
  4. If x survived, push it
BRUTEO(n²) resolving one adjacent collision at a time
→
OPTIMALO(n)
↕ SCROLL
vector<int> asteroidCollision(vector<int>& asteroids) {
    vector<int> st;                          // the survivors so far
    for (int x : asteroids) {
        bool alive = true;
        while (alive && x < 0 && !st.empty() && st.back() > 0) {
            if (st.back() < -x) { st.pop_back(); continue; }   // the → breaks
            if (st.back() == -x) st.pop_back();               // both break
            alive = false;                                    // x breaks
        }
        if (alive) st.push_back(x);
    }
    return st;
}
TIMEO(n)each asteroid pushed once and popped at most once
SPACEO(n)the stack of survivors
TRAP

Letting a left-mover hit another left-mover. [−2, −1] never collides: they move the same way. The loop must also check that the top moves right.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
22 / PROBLEM #08 · COLLIDE · MED

Car Fleet

MED collide ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Cars on one road, no overtaking. A car that catches a slower car ahead joins it and drives at its speed. Count the groups that arrive.

INTUITION

Sort by position, closest to the target first, and work out when each car would arrive alone. A car that would arrive no later than the fleet ahead catches it. A later one starts a new fleet.

STEPS
  1. Pair each position with its speed and sort, closest first
  2. t = (target − position) / speed
  3. t ≤ the fleet ahead's time: it joins
  4. t greater: push t, a new fleet
BRUTEO(n²) giving each car the latest arrival time among the cars ahead
→
OPTIMALO(n log n)
↕ SCROLL
int carFleet(int target, vector<int>& position, vector<int>& speed) {
    vector<pair<int, int>> car;
    for (int i = 0; i < position.size(); i++) car.push_back({position[i], speed[i]});
    sort(car.rbegin(), car.rend());          // closest to the target first
    long long d = 0, s = 1;                  // the fleet ahead arrives at d / s
    int fleets = 0;
    for (auto& c : car) {
        long long dc = target - c.first;     // this car would arrive at dc / c.second
        if (fleets == 0 || dc * s > d * c.second) {   // later, exactly: a new fleet
            fleets++;
            d = dc; s = c.second;
        }
    }
    return fleets;
}
TIMEO(n log n)the sort; the scan is O(n)
SPACEO(n)the cars and the fleet times
TRAP

Sorting by speed, or not sorting. Whether a car catches another depends on who is ahead, so the order must be by position. In input order, a car can be compared with one behind it.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
23 / DRILL UNIT 04 · Collisions and Fleets · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

target = 10, position = [6, 8], speed = [3, 2]. How many fleets?

The car at 8 arrives at t = 1. The car at 6 needs 4 / 3, so it never catches up.

DRILL 02 · TRACE

target = 10, position = [0, 4, 2], speed = [2, 1, 3]. How many fleets?

The car at 4 needs t = 6. The others would arrive at 8 / 3 and 5, both sooner, so both catch it.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
24 / MECHANISM UNIT 05 · KEEP IT INCREASING

A BIGGER DIGIT IN FRONT GOES FIRST

While k lasts, a digit bigger than the next is popped. The stack never falls, and any removals left over come off the end.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
25 / DRILL UNIT 05 · Keep It Increasing

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

removeKdigits("10200", 1)?

1 is bigger than the 0 after it, so it goes. The leading 0 of 0200 is then stripped.

DRILL 02 · TRACE

removeKdigits("12345", 2)?

The digits rise, so nothing is popped. Both removals come off the end.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
26 / PROBLEM #09 · GREEDY · MED

Remove K Digits

MED greedy ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Remove k digits to leave the smallest number. The leftmost digits weigh the most.

INTUITION

A digit bigger than the one after it should go, while removals are left. Keep the answer on a stack that never falls. Leftover removals come off the end, and leading zeros are stripped.

STEPS
  1. Read digit c
  2. While k > 0 and the top is bigger than c, pop it and spend one removal
  3. Push c
  4. Cut k more from the end, strip leading zeros, "0" if empty
BRUTEO(C(n, k) · n) trying every set of k digits
→
OPTIMALO(n)
↕ SCROLL
string removeKdigits(string num, int k) {
    string st;                               // the answer so far, never falling
    for (char c : num) {
        while (k > 0 && !st.empty() && st.back() > c) {
            st.pop_back();                   // a bigger digit before a smaller one
            k--;
        }
        st.push_back(c);
    }
    while (k > 0) { st.pop_back(); k--; }    // still owed: cut from the end
    int i = 0;
    while (i < st.size() && st[i] == '0') i++;
    string r = st.substr(i);
    return r.empty() ? "0" : r;
}
TIMEO(n)each digit pushed once and popped at most once
SPACEO(n)the stack of digits
TRAP

Forgetting the leftover k. On a rising number such as 12345 nothing is ever popped. The k removals are still owed and come off the end.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
27 / MECHANISM UNIT 06 · EACH ELEMENT'S SHARE

BOTH EDGES ARRIVE AT THE POP

When i pops j, the new top is j's left edge and i its right. arr[j] is the minimum of (j − left) · (i − j) subarrays.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
28 / DRILL UNIT 06 · Each Element's Share · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

arr = [2, 2]. Counted at the pop, how many subarrays does each 2 get?

The first gets [2]. The second gets its own [2] and [2, 2], because its left edge is −1. Three subarrays, each counted once.

DRILL 02 · TRACE

sumSubarrayMins([1, 2, 3])?

The minima are 1, 2, 3, 1, 2 and 1. The 1 is the minimum of three subarrays, the 2 of two.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
29 / PROBLEM #10 · CONTRIB · MED

Sum of Subarray Minimums

MED contrib ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The sum of the minimum of every subarray. There are n² / 2 subarrays, so count, for each element, how many of them it is the minimum of.

INTUITION

arr[j] is the minimum of every subarray that starts after the previous smaller value and ends before the next smaller-or-equal one. A stack of rising values finds both edges the moment j is popped.

STEPS
  1. Scan i = 0 … n, with a 0 at i = n that pops everything
  2. Pop j while arr[j] ≥ x; left is the new top, or −1
  3. Add arr[j] · (j − left) · (i − j)
  4. Push i; return the total mod 10⁹ + 7
BRUTEO(n²) extending each start with a running minimum
→
OPTIMALO(n)
↕ SCROLL
int sumSubarrayMins(vector<int>& arr) {
    const long long MOD = 1000000007;
    int n = arr.size();
    long long sum = 0;
    vector<int> st;                          // indices, values rise toward the top
    for (int i = 0; i <= n; i++) {           // i == n: a 0 that pops everything
        int x = i < n ? arr[i] : 0;
        while (!st.empty() && arr[st.back()] >= x) {
            int j = st.back(); st.pop_back();
            int left = st.empty() ? -1 : st.back();
            sum = (sum + (long long)arr[j] * (j - left) * (i - j)) % MOD;
        }
        st.push_back(i);
    }
    return sum;
}
TIMEO(n)each index pushed once and popped once
SPACEO(n)the stack
TRAP

Counting a tie twice. With equal values, one side must stop at “smaller” and the other at “smaller or equal”. The single stack does this already: left is strictly smaller, because an equal value was popped.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
30 / PROBLEM #11 · CONTRIB · MED

Sum of Subarray Ranges

MED contrib ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The sum of max − min over every subarray. Split it: the sum of the maxima minus the sum of the minima.

INTUITION

Each sum is unit 6 again. Run the contribution stack twice: once with values falling toward the top, adding each maximum's share, and once rising, taking off each minimum's.

STEPS
  1. sign = +1: pop while nums[top] ≤ nums[i]; add the share of each maximum
  2. sign = −1: pop while nums[top] ≥ nums[i]; take off the share of each minimum
  3. A share is nums[j] · (j − left) · (i − j); i = n empties the stack
  4. The total is the answer; it needs 64 bits
BRUTEO(n²) extending each start with a running maximum and minimum
→
OPTIMALO(n)
↕ SCROLL
long long subArrayRanges(vector<int>& nums) {
    int n = nums.size();
    long long total = 0;
    for (int sign : {1, -1}) {               // +1 adds the maxima, −1 takes the minima
        vector<int> st;
        for (int i = 0; i <= n; i++) {
            while (!st.empty() && (i == n || sign * nums[st.back()] <= sign * nums[i])) {
                int j = st.back(); st.pop_back();
                int left = st.empty() ? -1 : st.back();
                total += (long long)sign * nums[j] * (j - left) * (i - j);
            }
            st.push_back(i);
        }
    }
    return total;
}
TIMEO(n)two passes of the contribution stack
SPACEO(n)the stack
TRAP

A 32-bit total. One share can be 10⁹ · 500 · 500. The sum, and the product that makes each share, need long long before the multiply.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
31 / DRILL UNIT 06 · Each Element's Share · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

subArrayRanges([1, 3, 2])?

The single values give 0. Then [1, 3] gives 2, [3, 2] gives 1 and [1, 3, 2] gives 2.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
32 / MECHANISM UNIT 07 · THE WIDEST RECTANGLE

THE BAR BELOW IS THE LEFT EDGE

A lower bar pops each taller one. The popped bar's rectangle runs from just after the bar below it to just before the popper.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
33 / DRILL UNIT 07 · The Widest Rectangle · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

largestRectangleArea([2, 4])?

Height 2 across both bars is 4, and height 4 on its own is also 4.

DRILL 02 · TRACE

heights = [6, 2, 5, 4, 5, 1, 6]. The 1 at index 5 pops the bar of 4 at index 3. How wide is that bar's rectangle?

The bar below it on the stack is the 2 at index 1. So it spans indices 2 to 4, and its area is 12.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
34 / PROBLEM #12 · WIDTH · HARD

Largest Rectangle in Histogram

HARD width ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The largest rectangle under a histogram. Every rectangle is as tall as its lowest bar, so try each bar as that lowest one.

INTUITION

A bar's rectangle spreads left and right until a lower bar. Keep bars on a stack, rising toward the top. A lower bar pops each taller one, and the bar below it on the stack is its left edge.

STEPS
  1. Scan i = 0 … n, with a bar of 0 at i = n
  2. Pop j while h[j] ≥ h[i]
  3. Its width is i − left − 1, where left is the new top or −1
  4. Keep the best h[j] · width; push i
BRUTEO(n²) fixing the left edge and keeping a running minimum
→
OPTIMALO(n)
↕ SCROLL
int largestRectangleArea(vector<int>& heights) {
    vector<int>& h = heights;
    int n = h.size(), best = 0;
    vector<int> st;                          // bars still growing, rising upward
    for (int i = 0; i <= n; i++) {           // i == n: a bar of 0 ends them all
        int x = i < n ? h[i] : 0;
        while (!st.empty() && h[st.back()] >= x) {
            int j = st.back(); st.pop_back();
            int left = st.empty() ? -1 : st.back();
            best = max(best, h[j] * (i - left - 1));
        }
        st.push_back(i);
    }
    return best;
}
TIMEO(n)each bar pushed once and popped once
SPACEO(n)the stack
TRAP

Width i − j. That measures only from j rightwards. Bars to the left of j that are taller were popped earlier and still belong to its rectangle. The left edge is the bar below j on the stack.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
35 / PROBLEM #13 · WIDTH · HARD

Mike and Feet

HARD width ▶ SOLVE ON CODEFORCESCodeforces 547B, rated 1900.
SIGNAL — WHAT GIVES IT AWAY

For every group size x from 1 to n, find the largest possible minimum of a group of x neighbouring bears.

INTUITION

Turn it round. a[j] is the minimum of a run of exactly w bears, the run unit 7 measures. So best[w] ≥ a[j]. A size that fits in a run also fits in any longer one, so a sweep from the largest size down finishes it.

STEPS
  1. Unit 7's stack gives each a[j] its run width w
  2. best[w] = max(best[w], a[j])
  3. For x = n − 1 down to 1: best[x] = max(best[x], best[x + 1])
  4. Print best[1 … n]
BRUTEO(n²) sliding a window of each size with a running minimum
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<int> a(n + 1, 0), best(n + 2, 0), st;   // a[n] = 0 ends every run
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i <= n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) {
            int j = st.back(); st.pop_back();
            int left = st.empty() ? -1 : st.back();
            int w = i - left - 1;            // a[j] is the minimum of a run this wide
            best[w] = max(best[w], a[j]);
        }
        st.push_back(i);
    }
    for (int x = n - 1; x >= 1; x--) best[x] = max(best[x], best[x + 1]);
    for (int x = 1; x <= n; x++) cout << best[x] << (x < n ? ' ' : '\n');
}
TIMEO(n)one stack pass and one sweep
SPACEO(n)the stack and best
TRAP

Skipping the sweep. Some sizes are never a run's exact width, and their best stays 0. The answer for x is at least the answer for x + 1, so carry it down.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
36 / DRILL UNIT 07 · The Widest Rectangle · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Mike and Feet with n = 3 and heights 3 1 2. What is printed?

For size 1 the best is the 3 alone. Every group of 2 or 3 contains the 1.

DRILL 02 · BUG

A solution leaves out the backward sweep. What does it print on 2 1 2?

No run is exactly 2 wide, so best[2] stays 0. The sweep would carry best[3] = 1 down to it.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
37 / MECHANISM UNIT 08 · THE MONOTONIC DEQUE

EXPIRED AT THE FRONT, BEATEN AT THE BACK

Values fall from front to back. A bigger arrival removes the smaller ones behind it, and the front leaves when the window passes it.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
38 / DRILL UNIT 08 · The Monotonic Deque · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

maxSlidingWindow([9, 8, 7, 6], 2)?

Each window's maximum is its first value. Nothing is popped from the back; the front leaves as the window passes it.

DRILL 02 · RECALL

How many indices can the deque hold at once?

Every index in it is inside the window, and the window holds k.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
39 / DRILL UNIT 08 · The Monotonic Deque · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

nums = [4, 2, 3], k = 3. Which values are in the deque, front to back, after i = 2?

3 removes the 2 behind it, which can never be a maximum again. 4 is bigger, so it stays in front.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
40 / PROBLEM #14 · DEQUE · HARD

Sliding Window Maximum

HARD deque ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The maximum of every window of size k. A max-heap would cost log k per step; the window only ever loses its oldest value.

INTUITION

Keep indices in a deque with values falling from front to back. A value with a bigger one after it can never be a maximum again, so it leaves from the back. The front leaves once it is out of the window, and the front is always the maximum.

STEPS
  1. Drop the front if its index is i − k or less
  2. Pop the back while its value ≤ nums[i]
  3. Push i at the back
  4. Once i ≥ k − 1, record nums[front]
BRUTEO(n · k) scanning every window
→
OPTIMALO(n)
↕ SCROLL
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;                           // indices; values fall front to back
    vector<int> out;
    for (int i = 0; i < nums.size(); i++) {
        if (!dq.empty() && dq.front() <= i - k) dq.pop_front();   // out of the window
        while (!dq.empty() && nums[dq.back()] <= nums[i])
            dq.pop_back();                   // smaller and older: never a maximum
        dq.push_back(i);
        if (i >= k - 1) out.push_back(nums[dq.front()]);
    }
    return out;
}
TIMEO(n)each index enters and leaves the deque once
SPACEO(k)the deque, at most k indices
TRAP

Storing values in the deque. Then nothing says when the front has left the window, and a repeated value makes it worse. Store indices and read the values through them.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
41 / MECHANISM UNIT 09 · A DEQUE ON PREFIX SUMS

TAKE FROM THE FRONT, PRUNE FROM THE BACK

P rises along the deque. A front start that already reaches k is recorded and dropped; a back start with P ≥ P[j] can never win.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
42 / DRILL UNIT 09 · A Deque on Prefix Sums · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why can a sliding window not solve this problem?

Shrinking a window can raise its sum, and growing it can lower it. A window only works when growing never lowers the sum.

DRILL 02 · TRACE

nums = [2, −1, 2], k = 3. What is P, and the answer?

Only the whole array reaches 3: P[3] − P[0] = 3. P starts with the empty prefix, 0.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
43 / DRILL UNIT 09 · A Deque on Prefix Sums · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Start s leaves the back of the deque when P[s] ≥ P[j]. Why can s never be the best start?

For any later end, j gives a sum at least as large from a shorter subarray.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
44 / PROBLEM #15 · DEQUE · HARD

Shortest Subarray with Sum at Least K

HARD deque ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The shortest subarray with sum ≥ k, and the values can be negative. A sliding window fails: growing a window can lower its sum.

INTUITION

A sum is P[j] − P[s] over prefix sums. Keep start candidates in a deque with P rising. From the front, take every start that already reaches k, since no later end can beat it. From the back, drop a start whose P is at least P[j]: j starts later with a smaller prefix.

STEPS
  1. Build P with P[0] = 0
  2. While P[j] − P[front] ≥ k: record j − front, pop the front
  3. While P[back] ≥ P[j]: pop the back
  4. Push j; return the best, or −1
BRUTEO(n²) trying every subarray
→
OPTIMALO(n)
↕ SCROLL
int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> P(n + 1, 0);
    for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i];
    deque<int> dq;                           // starts; P rises front to back
    int best = INT_MAX;
    for (int j = 0; j <= n; j++) {
        while (!dq.empty() && P[j] - P[dq.front()] >= k) {
            best = min(best, j - dq.front());   // the shortest from this start
            dq.pop_front();
        }
        while (!dq.empty() && P[dq.back()] >= P[j])
            dq.pop_back();                   // later and smaller: always better
        dq.push_back(j);
    }
    return best == INT_MAX ? -1 : best;
}
TIMEO(n)each start enters and leaves the deque once
SPACEO(n)P and the deque
TRAP

A sliding window. With negatives, shrinking from the left can raise the sum and growing can lower it, so a window misses answers. On [84, −37, 32, 40, 95] with k = 167 the answer is the last three values; a window returns 5.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
45 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Nine moves, and each has a phrase in the statement that gives it away.

“NEXT GREATER” / “DAYS UNTIL WARMER”

a stack of values still waiting; the value that pops one is its answer

NEXT GREATERO(n)
THE SAME, BUT THE ARRAY WRAPS AROUND

read it twice with i % n; only the first lap pushes

AROUND THE CIRCLEO(n)
“HOW MANY DAYS IN A ROW, ENDING TODAY”

pop what today makes useless and add up what it carried

LOOKING BACKO(n)
THINGS MEET, AND ONE OF THEM BREAKS

the survivors on a stack; only the top can meet the next arrival

COLLISIONSO(n)
“REMOVE k DIGITS TO MAKE IT SMALLEST”

pop a bigger digit in front of a smaller one while k lasts

KEEP IT INCREASINGO(n)
A SUM OF EVERY SUBARRAY'S MINIMUM OR MAXIMUM

count each value's subarrays at the moment it is popped

EACH ELEMENT'S SHAREO(n)
THE LARGEST RECTANGLE, THE WIDEST RUN

the bar below on the stack is the left edge, the popper the right

THE WIDEST RECTANGLEO(n)
THE MAXIMUM OF EVERY WINDOW

a deque falling front to back; expired indices leave the front

MONOTONIC DEQUEO(n)
SHORTEST SUBARRAY WITH SUM ≥ k, NEGATIVES ALLOWED

prefix sums in a rising deque; take from the front, prune the back

DEQUE ON PREFIX SUMSO(n)
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
46 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

For each day, how many days ago was the price last higher than today's? Which move?

A stack of earlier prices, falling toward the top. Pop every price at most today's; the top is then the last higher one.

DRILL 02 · TRANSFER

Maximal Rectangle asks for the largest rectangle of 1s in a 0/1 matrix. Which move does it run once per row?

Row by row, count the 1s above each cell. That row is a histogram, and unit 7 finds its largest rectangle.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
47 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

dp[i] = nums[i] + the largest dp[j] among the k indices before i. Which move gives that largest value in O(1)?

The candidates form a sliding window of k values, and its maximum is the deque's front.

DRILL 02 · RECALL

The scan has a while loop inside a for loop. Why is it still O(n)?

All the inner loops together pop at most as many times as the outer loop pushes: n.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
48 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

VALUES WHERE INDICES BELONG

A distance, a width or a window needs positions. Push the index and read the value through it; a bare value cannot say where it was.

THE WRONG COMPARISON

Next greater pops the smaller values, so the stack falls. Nearest smaller pops the larger ones, so it rises. The other test keeps exactly the values that should go.

COUNTING A TIE TWICE

A contribution sum stops at “smaller” on one side and “smaller or equal” on the other. Strict on both sides counts an equal pair's subarrays twice.

NO SENTINEL AT THE END

Values still on the stack when the scan ends are never popped, so never counted. A 0 at i = n, or a loop that drains the stack, settles them.

A STALE FRONT

The front of a deque can fall out of the window. Drop it when dq.front() ≤ i − k, before reading the maximum.

REMOVALS LEFT OVER

A rising number such as 12345 pops nothing. The k removals are still owed and come off the end.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
49 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Nine moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Next greater
O(n)
O(n)
pop the smaller values; the popper is their answer
Around the circle
O(n)
O(n)
read 2n values with i % n; push on the first lap only
Looking back
O(n)
O(n)
pop what today makes useless; the top is the answer
Collisions
O(n)
O(n)
only the top survivor meets the next arrival
Keep it increasing
O(n)
O(n)
pop a bigger digit while k lasts; cut what is still owed
Each element's share
O(n)
O(n)
value × (j − left) × (right − j), counted at the pop
The widest rectangle
O(n)
O(n)
width i − left − 1 at the pop; a bar of 0 at the end
Monotonic deque
O(n)
O(k)
the back drops the beaten, the front drops the expired
Deque on prefix sums
O(n)
O(n)
shortest sum ≥ k with negatives; P rises in the deque
INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
50 / CLOSE MODULE 13 · MONOTONIC STACK & DEQUE

POP IT YOURSELF

A value waited until something bigger popped it; a second lap went round the circle; a popped day handed over its span; survivors met at the top; a number kept its digits rising; each value counted the subarrays it was the minimum of; the bar below became a left edge; and a deque dropped the beaten at the back and the expired at the front. Maximal Rectangle (DP 4) runs unit 7 once per row, and Trapping Rain Water (module 5) has a stack solution too.

00%
OF THIS DECK SOLVED
← ALL TOPICS← STACKS & QUEUESSLIDING WINDOW →

Module 13. Fifteen problems: thirteen on LeetCode, one on CSES and one on Codeforces. Next: sliding window and two pointers.

INVARIANT · MONOTONIC STACK & DEQUE · WAITING FOR SOMETHING BIGGER · MONOTONIC STACK & DEQUE
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 13 · MONOTONIC STACK & DEQUE

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.