Week 3
Stack & Binary Search
Two small tools with a huge reach. A stack remembers the most recent unfinished thing; binary search finds things in sorted data by halving the search every step.
- Stack for matching pairs
- Auxiliary stack (running min or max)
- Stack-based expression evaluation
- Monotonic stack
- Sort, then stack to merge groups
- Classic binary search
- 2D matrix as a 1D sorted array
- Binary search on a rotated array
This week has two halves. The first is the stack, a data structure (a way of organising data) that is perfect whenever “the most recent thing” matters. The second is binary search, an algorithm (a recipe of steps) that finds things in sorted data absurdly fast. Each pattern below links to the problems that use it, and each problem page has a step-by-step visualizer.
Think of a stack of plates. You can only do three things with it:
- push: put a plate on top.
- pop: take the top plate off.
- peek: look at the top plate without taking it.
You can’t pull a plate from the middle. So the plate you take off is always the last one you put on. This rule has a name: LIFO, “last in, first out”.
- 3
- 7
- 5
You don’t need a special library. A JavaScript array or a Python list already is a stack, as long as you only add and remove at the end: the end of the array is the top of the stack.
An array / list used as a stack
const stack = []; // an empty array, used as a stackstack.push(3); // put 3 on topstack.push(7);stack.push(5);const peeked = stack.at(-1); // peek: read the top, don't remove itconst first = stack.pop(); // pop: remove the top and hand it backconst second = stack.pop();const isEmpty = stack.length === 0;stack = [] # an empty list, used as a stackstack.append(3) # put 3 on topstack.append(7)stack.append(5)peeked = stack[-1] # peek: read the top, don't remove itfirst = stack.pop() # pop: remove the top and hand it backsecond = stack.pop()is_empty = len(stack) == 0Step through it. Watch the top change, and notice that pop always returns the
newest item:
push, peek, pop
- empty
- size
- 0
- top
- —
- Just pushed
- Top, being read
Start with an empty stack. In code it's just an empty array (JavaScript) or list (Python).
Which line is running?
Running now: const stack = []; // an empty array, used as a stackstack.push(3); // put 3 on topstack.push(7);stack.push(5);const peeked = stack.at(-1); // peek: read the top, don't remove itconst first = stack.pop(); // pop: remove the top and hand it backconst second = stack.pop();const isEmpty = stack.length === 0;| operation | JavaScript | Python | cost |
|---|---|---|---|
| push | stack.push(x) | stack.append(x) | O(1) |
| pop | stack.pop() | stack.pop() | O(1) |
| peek | stack.at(-1) | stack[-1] | O(1) |
| is it empty? | stack.length === 0 | not stack | O(1) |
O(1) means “a fixed number of steps, however big the stack is”. All four operations are instant, which is why stacks are so useful.
When does a stack fit? Whenever you have unfinished things and the one you must deal with next is the most recent one: an opener waiting for its closer, numbers waiting for an operator, days waiting for a warmer day.
Play a game: I pick a number from 1 to 100, you guess, and I say “higher” or “lower”. Guessing 1, 2, 3, … might take 100 guesses. The smart first guess is 50: whatever I answer, half the numbers are gone. Then 25 or 75, and so on. You never need more than 7 guesses.
That’s binary search: look at the middle of what’s left, and use the answer to throw away half. “Binary” means “two”: every step splits the range in two.
Throwing half away is only safe if one look tells you which half the answer can’t be in. In a sorted array, if the middle is too small, everything to its left is even smaller, so the whole left half goes.
More generally, binary search works whenever you can ask a yes/no question about
each position whose answer flips only once: “no, no, no, … yes, yes, yes”.
That’s called monotonic (“moving in one direction only”). In
[1, 3, 5, 7, 9, 11], the question “is it at least 7?” is:
- 10
- 31
- 52
- 73
- 94
- 115
- no0
- no1
- no2
- yes3
- yes4
- yes5
Week 4 uses this idea to binary search things that aren’t even arrays (“binary search on the answer”). This week we stick to arrays.
Binary search takes O(log n) time. log₂ n (“log base 2 of n”) is simply the answer to: how many times can you halve n before you get down to 1?
- 8 → 4 → 2 → 1: three halvings, so log₂ 8 = 3.
- 16 → 8 → 4 → 2 → 1: four halvings, so log₂ 16 = 4.
- 1,000 → 500 → 250 → … → 1: 9 halvings (log₂ 1,000 is about 9.97; we round down).
- 1,000,000 → 500,000 → … → 1: 19 halvings (log₂ 1,000,000 is about 19.93).
Binary search needs one more look than that: after the last halving, one item is left and you still have to check it. So in the worst case it takes ⌊log₂ n⌋ + 1 looks (log₂ n rounded down, plus one), which is “about log₂ n”. For 8 items that’s 3 + 1 = 4 looks; for 16 items, 4 + 1 = 5, the “five guesses at most” in the picture above.
| n (items) | check every item: O(n) | binary search: O(log n) |
|---|---|---|
| 8 | 8 | 4 |
| 16 | 16 | 5 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
Double the input and binary search needs just one more step. That’s why interviewers love it.
Things that open and later close (brackets, HTML tags, function calls) must close in reverse order: the most recently opened one closes first. Push each opener on a stack; when a closer arrives, it must match the top.
Pattern
Stack for matching pairs
Use it when: every closer must match the most recent opener that is still open.
Signal words
- “valid parentheses”
- “balanced”
- “matching brackets”
- “nested”
- “remove adjacent duplicates”
Template: matching pairs
function isBalanced(s) { const opener = { ")": "(", "]": "[", "}": "{" }; // closer -> opener const stack = []; for (const ch of s) { if (!(ch in opener)) { stack.push(ch); // an opener waits on the stack } else if (stack.length === 0 || stack.pop() !== opener[ch]) { return false; // nothing to close, or the wrong kind } } return stack.length === 0; // nothing may be left open}def is_balanced(s): opener = {")": "(", "]": "[", "}": "{"} # closer -> opener stack = [] for ch in s: if ch not in opener: stack.append(ch) # an opener waits on the stack elif not stack or stack.pop() != opener[ch]: return False # nothing to close, or the wrong kind return not stack # nothing may be left openUsed in: Valid Parentheses.
An auxiliary stack is a helper stack that moves in lockstep with the main one. For each item pushed on the main stack, it stores a summary of everything from the bottom up to that item, such as the minimum so far. Because a stack only changes at the top, those summaries never go stale.
Pattern
Auxiliary stack (running min or max)
Use it when: you need the min or max of a stack at any moment, in O(1), while it keeps changing.
Signal words
- “design a stack”
- “getMin in constant time”
- “max stack”
- “O(1) for each operation”
Template: stack with a running minimum
class MinStack { constructor() { this.stack = []; this.mins = []; // mins[i] = smallest of stack[0..i] } push(val) { this.stack.push(val); this.mins.push(this.mins.length ? Math.min(val, this.mins.at(-1)) : val); } pop() { this.stack.pop(); this.mins.pop(); // always together } getMin() { return this.mins.at(-1); }}class MinStack: def __init__(self): self.stack = [] self.mins = [] # mins[i] = smallest of stack[0..i] def push(self, val): self.stack.append(val) self.mins.append(min(val, self.mins[-1]) if self.mins else val) def pop(self): self.stack.pop() self.mins.pop() # always together def getMin(self): return self.mins[-1]- 5
- 2
- 8
- 5
- 2
- 2
Used in: Min Stack.
When an expression is written with each operator after its two values
(postfix or Reverse Polish Notation, like 2 1 + 3 *), you can evaluate
it in one pass: values wait on a stack, and each operator pops the two most
recent ones and pushes the result back.
Pattern
Stack-based expression evaluation
Use it when: you process tokens where each operation consumes the most recent values (postfix maths, calculators, simplifying file paths).
Signal words
- “reverse Polish notation”
- “postfix”
- “evaluate the expression”
- “operands and operators”
Template: evaluate postfix
function evalPostfix(tokens) { const stack = []; for (const t of tokens) { if (["+", "-", "*", "/"].includes(t)) { const b = stack.pop(); // popped first = the SECOND value const a = stack.pop(); if (t === "+") stack.push(a + b); else if (t === "-") stack.push(a - b); else if (t === "*") stack.push(a * b); else stack.push(Math.trunc(a / b)); // toward zero } else { stack.push(Number(t)); } } return stack[0];}def eval_postfix(tokens): stack = [] for t in tokens: if t in ("+", "-", "*", "/"): b = stack.pop() # popped first = the SECOND value a = stack.pop() if t == "+": stack.append(a + b) elif t == "-": stack.append(a - b) elif t == "*": stack.append(a * b) else: stack.append(int(a / b)) # toward zero else: stack.append(int(t)) return stack[0]- 2
- 2
- 1
- 3
- 3
- 3
- 9
Used in: Evaluate Reverse Polish Notation.
A monotonic stack keeps its items in one order from bottom to top, always decreasing or always increasing. Before pushing a new item, you pop everything that would break the order, and each pop is a discovery: the new item is the “next greater” (or “next smaller”) element for the item you popped.
Pattern
Monotonic stack (next greater element)
Use it when: for every item you need the next (or previous) item that is bigger or smaller than it.
Signal words
- “next greater element”
- “next warmer day”
- “how many days until”
- “stock span”
- “nearest smaller to the left”
Template: next greater element
function nextGreater(nums) { const result = new Array(nums.length).fill(-1); // -1 = none const stack = []; // indexes; their values decrease bottom -> top for (let i = 0; i < nums.length; i++) { while (stack.length > 0 && nums[i] > nums[stack.at(-1)]) { result[stack.pop()] = nums[i]; // nums[i] answers that index } stack.push(i); } return result;}def next_greater(nums): result = [-1] * len(nums) # -1 = none stack = [] # indexes; their values decrease bottom -> top for i, x in enumerate(nums): while stack and x > nums[stack[-1]]: result[stack.pop()] = x # x answers that index stack.append(i) return resultFlip the comparison for the other variants: < for next smaller (keep an
increasing stack). Walk from the right, or read the top before pushing, for the
previous greater/smaller.
Used in: Daily Temperatures, and in Car Fleet the stack of arrival times is monotonic too.
Some problems are a mess in input order but simple once sorted: after sorting, each item only interacts with the group right next to it. Walk through the sorted items with a stack of groups; each item either starts a new group (push) or merges into the group on top.
Pattern
Sort, then stack to merge groups
Use it when: items only affect their neighbours once put in order, and some of them merge (fleets, overlapping ranges, collisions).
Signal words
- “fleet”
- “catch up”
- “cannot pass”
- “merge”
- “how many groups”
Template: car-fleet style merging
function countFleets(target, position, speed) { const cars = position.map((p, i) => [p, (target - p) / speed[i]]); cars.sort((a, b) => b[0] - a[0]); // front of the road first const stack = []; // one arrival time per group for (const [, time] of cars) { if (stack.length === 0 || time > stack.at(-1)) { stack.push(time); // can't reach the group ahead: new group } // else: merges into the group on top } return stack.length;}def count_fleets(target, position, speed): cars = sorted(zip(position, speed), reverse=True) # front first stack = [] # one arrival time per group for p, s in cars: time = (target - p) / s if not stack or time > stack[-1]: stack.append(time) # can't reach the group ahead: new group # else: merges into the group on top return len(stack)Used in: Car Fleet.
Search a sorted array for a value by keeping a range lo..hi where the value
must be (if it exists), and halving that range every round.
Pattern
Classic binary search
Use it when: the data is sorted (or a yes/no question flips once) and you need better than O(n).
Signal words
- “sorted array”
- “O(log n)”
- “find the index of”
- “search”
- “first / last position”
This is the one template to memorise. Every other binary search this week and next is a small change to it.
Template: classic binary search
function search(nums, target) { let lo = 0; let hi = nums.length - 1; // the target, if present, is in nums[lo..hi] while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { lo = mid + 1; // mid is too small: drop it and everything left of it } else { hi = mid - 1; // mid is too big: drop it and everything right of it } } return -1; // the range is empty: the target is not here}def search(nums, target): lo, hi = 0, len(nums) - 1 # the target, if present, is in nums[lo..hi] while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid elif nums[mid] < target: lo = mid + 1 # mid is too small: drop it and everything left of it else: hi = mid - 1 # mid is too big: drop it and everything right of it return -1 # the range is empty: the target is not hereA loop invariant is a promise that is true before the loop starts and stays true after every round. Here it is:
Every line of the template exists to keep that promise:
- Start
lo = 0,hi = length − 1: the whole array, so the promise is true. nums[mid] < target:midand everything left of it are too small, so the target can only be inmid + 1..hi. Settinglo = mid + 1keeps the promise.nums[mid] > target: by the same logic,hi = mid − 1keeps it.lo <= hi: the rangelo..histill has at least one item. Whenlo > hi, the range is empty, and the promise says “if it’s in the array, it’s in this empty range”. So it isn’t in the array: return-1.mid = lo + (hi − lo) // 2: the middle, rounded down. It’s always betweenloandhi, so the range shrinks by at least one every round and the loop must end.
Here it is running on a sorted array. The shaded block is lo..hi; faded items
have been ruled out:
Binary search: halve the range each round
nums = [1, 3, 5, 7, 9, 11, 13], target = 11
- 10
- 31
- 52
- 73
- 94
- 115
- 136
- target
- 11
- lo
- 0
- hi
- 6
- mid
- —
- nums[mid]
- —
- items left
- 7hi − lo + 1
- rounds
- 0
- result
- —
- Still possible (lo..hi)
- mid, being checked
- Thrown away
- Target
- Not the target
We look for 11. If it's anywhere, it's somewhere in nums[lo..hi]. At the start that's the whole array: lo = 0, hi = 6.
Which line is running?
function search(nums, target) { let lo = 0;Running now: let hi = nums.length - 1; // the target, if present, is in nums[lo..hi] while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { lo = mid + 1; // mid is too small: drop it and everything left of it } else { hi = mid - 1; // mid is too big: drop it and everything right of it } } return -1; // the range is empty: the target is not here}Used in: Binary Search, Search a 2D Matrix, and (in a boundary-finding variant) Find Minimum in Rotated Sorted Array. Week 4 builds on it: week 4.
If a grid with m rows and n columns is sorted in reading order (each row
sorted, and each row starting after the previous one ends), it’s secretly one
sorted list of m × n numbers. Binary search positions 0..m × n − 1 and convert
each position to a cell on the fly.
Pattern
2D matrix as a 1D sorted array
Use it when: each row is sorted and each row's first number is bigger than the previous row's last number.
Signal words
- “m x n matrix”
- “rows sorted”
- “each row starts after the previous row ends”
Template: the index mapping
// position k (0 .. m*n - 1) <-> cell [row, col]const row = Math.floor(k / n); // full rows before kconst col = k % n; // steps along that rowconst k2 = row * n + col; // and back again# position k (0 .. m*n - 1) <-> cell [row, col]row = k // n # full rows before kcol = k % n # steps along that rowk2 = row * n + col # and back again| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 4 | 5 | 6 | 7 |
| 2 | 8 | 9 | 10 | 11 |
Used in: Search a 2D Matrix.
A sorted array that has been rotated (some items moved from the front to the
back) looks like two rising runs with a drop, a “cliff”, between them:
[4, 5, 6, 7, 0, 1, 2]. It isn’t sorted, but comparing nums[mid] with the
right end nums[hi] tells you which side of the cliff mid is on.
Pattern
Binary search on a rotated array
Use it when: a sorted array was rotated and you need the minimum, the rotation point, or a target, in O(log n).
Signal words
- “rotated sorted array”
- “rotated between 1 and n times”
- “pivot”
- “unique elements”
- “O(log n)”
Template: find the minimum (the bottom of the cliff)
function findMin(nums) { let lo = 0; let hi = nums.length - 1; // the minimum is in nums[lo..hi] while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] > nums[hi]) { lo = mid + 1; // cliff is right of mid } else { hi = mid; // mid..hi rises: min is mid or left of it } } return nums[lo];}def find_min(nums): lo, hi = 0, len(nums) - 1 # the minimum is in nums[lo..hi] while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] > nums[hi]: lo = mid + 1 # cliff is right of mid else: hi = mid # mid..hi rises: min is mid or left of it return nums[lo]Notice this template is not the classic one: we’re narrowing down to one
position, not testing for a value. So the loop is lo < hi and one side is
hi = mid (mid might be the answer). The survival guide below explains when to
use which.
Used in: Find Minimum in Rotated Sorted Array. Week 4’s Search in Rotated Sorted Array uses the same “which side is sorted?” question to search for a target: see week 4.
An off-by-one bug is being wrong by exactly one: one index too far, one round too few. Binary search is famous for them. Here’s how to never get stuck.
| Find an exact value | Narrow down to one position | |
|---|---|---|
| example | Binary Search, 2D Matrix | Find Minimum in Rotated Array |
| start | lo = 0, hi = n − 1 | lo = 0, hi = n − 1 |
| loop while | lo <= hi | lo < hi |
| moves | lo = mid + 1, hi = mid − 1 | lo = mid + 1, hi = mid |
| ends when | lo > hi (empty range) | lo == hi (one candidate) |
| answer | return mid inside the loop, else −1 | return lo after the loop |
Each column is consistent with itself. The bugs come from taking one row from each column.
- 50
- 30
- 81
- 40
- 91
- 10
- 31
- 52
- 73
Before you say “done”, trace your code on these by hand:
- One item, target present and absent:
[5]with 5 and with 2. - Two items, target in each position:
[3, 8]with 3 and with 8. - Target smaller than everything and bigger than everything.
- Ask: “does every branch make the range smaller?” If any branch can leave
loandhiunchanged, it can loop forever.
Here’s a suggested order. It alternates between the two halves so each new problem adds one new idea on top of something you’ve just practised.
- Valid Parentheses (Easy). The purest stack problem: push, pop, compare. Start here.
- Binary Search (Easy). The classic template. Get it into your fingers; you’ll reuse it three more times.
- Min Stack (Medium). Back to stacks, plus one new idea: a helper stack. Also your first “design a class” problem.
- Evaluate Reverse Polish Notation (Medium). A stack of values instead of brackets. Short, but full of small traps (operand order, division).
- Search a 2D Matrix (Medium). The binary search template, unchanged, plus an index mapping.
- Daily Temperatures (Medium). The monotonic stack: the biggest new idea of the week. Take your time with the visualizer.
- Find Minimum in Rotated Sorted Array (Medium). Binary search on data that isn’t fully sorted, and the second loop style (
lo < hi). Read the survival guide first. - Car Fleet (Medium). Combines sorting, a bit of physics and a monotonic stack. The best finale.
If you finish early, go back to problems 2 and 7 and write both binary search templates from memory, then trace the 30-second checklist on each. That habit pays off all through week 4.
This week's problems
0 of 8 done
Check whether every bracket in a string is closed by the right kind of bracket, in the right order.
Build a stack that can also tell you its smallest value in one step, at any moment.
Work out the value of a maths expression written with the operator after its two numbers, like "2 1 + 3 *".
For each day, count how many days you have to wait for a warmer one.
Cars on a one-lane road can't overtake, so fast cars bunch up behind slow ones. Count how many groups arrive at the finish.
Find a number in a sorted array by repeatedly checking the middle and throwing away the half that can't contain it.
Find a number in a grid whose rows are sorted and follow on from each other, using one binary search.
A sorted array was cut in two and the halves swapped. Find its smallest number in O(log n) by binary searching for the cut.