Skip to content
16-Week DSA Roadmap

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.

What is a stack?

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”.

stack
  1. 3
  2. 7
  3. 5
A stack drawn the way we'll draw it all week: the bottom is the oldest item, the top is the newest. Only the top can be read or removed.

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) == 0

Step through it. Watch the top change, and notice that pop always returns the newest item:

push, peek, pop

stack
  1. empty
variables
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).

Step 1 / 8

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;
operationJavaScriptPythoncost
pushstack.push(x)stack.append(x)O(1)
popstack.pop()stack.pop()O(1)
peekstack.at(-1)stack[-1]O(1)
is it empty?stack.length === 0not stackO(1)
The four stack operations and what they cost

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.

16 left123456789101112131415168 left123456789101112131415163 left123456789101112131415161 left12345678910111213141516
Finding 11 among 1–16. Purple is the guess, shaded cells are still possible, faded cells are ruled out. 16 → 8 → 4 → 2 → 1: five guesses at most.

Why it needs sorted (or “monotonic”) data

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:

nums
  1. 10
  2. 31
  3. 52
  4. 73
  5. 94
  6. 115
nums[i] ≥ 7 ?
  1. no0
  2. no1
  3. no2
  4. yes3
  5. yes4
  6. yes5
'Is nums[i] ≥ 7?' answers no, no, no, then yes from index 3 on. Because it flips exactly once, binary search can find the flip point.

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.

Big-O refresher: O(log n)

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)
884
16165
1,0001,00010
1,000,0001,000,00020
1,000,000,0001,000,000,00030
Worst-case number of looks to find an item

Double the input and binary search needs just one more step. That’s why interviewers love it.

Pattern: Stack for matching pairs

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

Template

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 open
{0[1(2)3]4(5)6}7
Each arc joins an opener to its closer. Arcs nest but never cross; that's exactly what 'balanced' means, and exactly what a stack checks.

Used in: Valid Parentheses.

Pattern: Auxiliary stack (running min or max)

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)

Template

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]
stack
  1. 5
  2. 2
  3. 8
mins
  1. 5
  2. 2
  3. 2
After pushing 5, 2, 8: the value stack and its helper. mins never goes up, and its top is always the current minimum (2). Pop the 8 and the 2 underneath in mins is still right.

Used in: Min Stack.

Pattern: Stack-based expression evaluation

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

Template

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]
after 2
  1. 2
after 1
  1. 2
  2. 1
after +
  1. 3
after 3
  1. 3
  2. 3
after *
  1. 9
2 1 + 3 * after each token. The + eats 2 and 1 and leaves 3; the * eats 3 and 3 and leaves 9.

Used in: Evaluate Reverse Polish Notation.

Pattern: Monotonic stack

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)

Template

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 result
2501515−123434−14
nums = [2, 1, 5, 3, 4]. The number above each bar is its next greater element (−1 = none). 5 arrives and answers both 1 and 2 at once; 4 answers 3.

Flip 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.

Pattern: Sort, then stack to merge groups

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

Template

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)
1006htime →position →BCA
Position over time for target = 10, cars at 0, 2 and 4 with speeds 2, 3 and 1. The two fast cars catch the slow one at the front, and all three lines merge into one fleet.

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

Template

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 here

The loop invariant

A 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: mid and everything left of it are too small, so the target can only be in mid + 1..hi. Setting lo = mid + 1 keeps the promise.
  • nums[mid] > target: by the same logic, hi = mid − 1 keeps it.
  • lo <= hi: the range lo..hi still has at least one item. When lo > 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 between lo and hi, 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

nums
  1. 10
  2. 31
  3. 52
  4. 73
  5. 94
  6. 115
  7. 136
variables
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.

Step 1 / 5

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.

Pattern: 2D matrix as a 1D sorted array

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

Template

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
0123
0
0
1
2
3
1
4
5
6
7
2
8
9
10
11
Each cell shows its position k in a 3 × 4 grid (n = 4). Position 6 is row 6 // 4 = 1, column 6 % 4 = 2.

Used in: Search a 2D Matrix.

Pattern: Binary search on a rotated array

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

Template

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]
40516273041526cliff↑mid↑hi
nums[mid] = 7 is bigger than nums[hi] = 2, so a drop must happen between them: the cliff (and the minimum) is right of mid.

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.

Off-by-one survival guide

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.

Two templates, never mix them

Find an exact valueNarrow down to one position
exampleBinary Search, 2D MatrixFind Minimum in Rotated Array
startlo = 0, hi = n − 1lo = 0, hi = n − 1
loop whilelo <= hilo < hi
moveslo = mid + 1, hi = mid − 1lo = mid + 1, hi = mid
ends whenlo > hi (empty range)lo == hi (one candidate)
answerreturn mid inside the loop, else −1return lo after the loop
Pick the template by the question you're asking

Each column is consistent with itself. The bugs come from taking one row from each column.

Trap 1: lo < hi in the exact-value template

nums
  1. 50
nums = [5], target = 5. lo = hi = 0. With 'while lo < hi' the loop never runs and we return −1, although the 5 is right there. One-item ranges need 'lo <= hi'.

Trap 2: hi = mid with lo <= hi

nums
  1. 30
  2. 81
nums = [3, 8], target = 1. Round 1: mid = 0, 3 > 1, so hi = mid = 0. Round 2: lo = hi = mid = 0, 3 > 1, hi = mid = 0 again. Nothing changes: an infinite loop. With 'lo <= hi', always use hi = mid − 1.

Trap 3: lo = mid when mid rounds down

nums
  1. 40
  2. 91
Two items left: lo = 0, hi = 1, so mid = 0 (rounded down). If a branch sets lo = mid, lo stays 0 forever. Moving lo must always be lo = mid + 1 (or, if you really need lo = mid, round mid UP).

Trap 4: hi = nums.length

nums
  1. 10
  2. 31
  3. 52
  4. 73
The last index of a 4-item array is 3, not 4. With hi = 4, mid can become 4, and nums[4] doesn't exist (undefined in JS, IndexError in Python).

The 30-second checklist

Before you say “done”, trace your code on these by hand:

  1. One item, target present and absent: [5] with 5 and with 2.
  2. Two items, target in each position: [3, 8] with 3 and with 8.
  3. Target smaller than everything and bigger than everything.
  4. Ask: “does every branch make the range smaller?” If any branch can leave lo and hi unchanged, it can loop forever.

Problem roadmap

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.

  1. Valid Parentheses (Easy). The purest stack problem: push, pop, compare. Start here.
  2. Binary Search (Easy). The classic template. Get it into your fingers; you’ll reuse it three more times.
  3. Min Stack (Medium). Back to stacks, plus one new idea: a helper stack. Also your first “design a class” problem.
  4. Evaluate Reverse Polish Notation (Medium). A stack of values instead of brackets. Short, but full of small traps (operand order, division).
  5. Search a 2D Matrix (Medium). The binary search template, unchanged, plus an index mapping.
  6. Daily Temperatures (Medium). The monotonic stack: the biggest new idea of the week. Take your time with the visualizer.
  7. 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.
  8. 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

  1. Check whether every bracket in a string is closed by the right kind of bracket, in the right order.

  2. 2. #155Min StackMedium

    Build a stack that can also tell you its smallest value in one step, at any moment.

  3. Work out the value of a maths expression written with the operator after its two numbers, like "2 1 + 3 *".

  4. 4. #739Daily TemperaturesMedium

    For each day, count how many days you have to wait for a warmer one.

  5. 5. #853Car FleetMedium

    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.

  6. 6. #704Binary SearchEasy

    Find a number in a sorted array by repeatedly checking the middle and throwing away the half that can't contain it.

  7. 7. #74Search a 2D MatrixMedium

    Find a number in a grid whose rows are sorted and follow on from each other, using one binary search.

  8. 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.