INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE
01
00/15
01 / COVER MODULE 21 · GREEDY
INVARIANT · MODULE 21 · GREEDY
TAKE THE BEST CHOICE NOW

A greedy solution makes each choice once and never goes back. It is right only when some argument shows the choice is safe: it leaves at least as much for later, or swapping it into any other answer costs nothing. Eleven moves, fifteen problems.

15Problems
5Families
11Units
12Live 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 · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
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.

KEEP THE MOST OPTIONS · 03
CARRY THE REACH · 03
BOUNDS AND PASSES · 03
THE ORDER A SWAP PROVES · 04
EVERYTHING UP TO REACH · 02
SOLVED HAS A JUDGE LINK
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
03 / MECHANISM UNIT 01 · PAY WITH THE BILL YOU NEED LEAST

SPEND THE 10, KEEP THE 5

A 20 can be paid with a 10 and a 5 or with three 5s. Both work now, but a 5 is also change for a 10 and a 10 is not, so the 10 goes first and the drawer keeps the bill that pays for more.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
04 / DRILL UNIT 01 · Pay With the Bill You Need Least

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

lemonadeChange([5, 5, 10, 10, 20])?

After the two 10s the drawer holds two 10s and no 5. The 20 is owed 15, and no mix of 10s makes 15.

DRILL 02 · RECALL

Why is a 20 paid with a 10 and a 5 rather than three 5s?

A 10 is only ever change for a 20, but a 5 pays for a 10 as well. Spending the 10 keeps the more useful bill.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
05 / PROBLEM #01 · OPTIONS · EASY

Lemonade Change

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

Customers pay 5, 10 or 20 for a 5 lemonade, in a fixed order, and the drawer starts empty. Can everyone get change?

INTUITION

A 10 is owed one 5. A 20 is owed 15, as a 10 and a 5 or as three 5s. A 5 can be change for a 10 or a 20, but a 10 only for a 20, so the 10 is the bill to spend first. Twenties are never change at all, so only the 5s and 10s are counted.

STEPS
  1. Count the 5s and the 10s in the drawer
  2. A 5: keep it
  3. A 10: give back a 5, or fail if there is none, and keep the 10
  4. A 20: give a 10 and a 5 if possible, else three 5s, else fail
BRUTEO(2ⁿ) trying both ways to pay every 20
→
OPTIMALO(n)
↕ SCROLL
bool lemonadeChange(vector<int>& bills) {
    int five = 0, ten = 0;
    for (int b : bills) {
        if (b == 5) five++;                // no change owed
        else if (b == 10) {
            if (five == 0) return false;
            five--; ten++;
        } else {                           // a 20: 15 is owed
            if (ten > 0 && five > 0) { ten--; five--; }   // spend the 10 first
            else if (five >= 3) five -= 3;
            else return false;
        }
    }
    return true;
}
TIMEO(n)one pass over the bills
SPACEO(1)two counters
TRAP

Three 5s before a 10 and a 5. Both pay a 20 now, but spending three 5s can leave no 5 for the next 10. On 5, 5, 5, 5, 10, 20, 10 the wrong order fails at the last customer.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
06 / MECHANISM UNIT 02 · LEAVE ROOM FOR WHAT COMES NEXT

FALL LEFT IF YOU CAN, RIGHT IF YOU MUST

Read the trees left to right and remember the last occupied point. Room on the left is no use to any later tree, so take it. Falling right can cost only the next tree, which this one replaces.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
07 / DRILL UNIT 02 · Leave Room for What Comes Next · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

canPlaceFlowers([0, 0, 1, 0, 0, 0, 0], 3)?

Plots 0, 4 and 6. Plot 3 sits beside the flower at 2, and planting at 4 still leaves plot 6 free.

DRILL 02 · RECALL

In Woodcutters, why is falling left tried before falling right?

Every later tree stands further right, so the space to the left of this one can only ever be used by this one.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
08 / PROBLEM #02 · OPTIONS · EASY

Can Place Flowers

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

Plant n flowers in a bed of 0s and 1s so that no two flowers are adjacent. Is there room?

INTUITION

Read the bed left to right and plant in every empty plot whose neighbours are empty. Planting at the first legal plot never hurts. Any plan that plants later in the same run can move that flower left to here, and the plot after it is then free for the next.

STEPS
  1. Walk the plots left to right
  2. Skip a plot holding a flower
  3. An empty plot whose left and right are empty, or off the edge, gets a flower
  4. Mark it planted and count it; stop once n are planted
BRUTEO(2ᵐ) trying every set of plots
→
OPTIMALO(m)
↕ SCROLL
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    int m = flowerbed.size();
    for (int i = 0; i < m && n > 0; i++) {
        if (flowerbed[i] == 1) continue;
        bool left = i == 0 || flowerbed[i - 1] == 0;
        bool right = i == m - 1 || flowerbed[i + 1] == 0;
        if (left && right) { flowerbed[i] = 1; n--; }   // the first legal plot
    }
    return n <= 0;
}
TIMEO(m)one pass over the m plots
SPACEO(1)the bed is marked in place
TRAP

Forgetting to mark the plot. Without flowerbed[i] = 1, the next plot still sees an empty left neighbour, and [0, 0, 0] seems to hold three flowers instead of two.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
09 / PROBLEM #03 · OPTIONS · MED

Woodcutters

MED options ▶ SOLVE ON CODEFORCESCodeforces 545C, rated 1500.
SIGNAL — WHAT GIVES IT AWAY

Trees stand at increasing points along a road. Each may fall left or right by its height, or stand, and no fallen tree may cover an occupied point. Fell as many as you can.

INTUITION

Go left to right and remember prev, the last point taken. Fall left whenever x − h > prev: that space is behind every tree still to come, so it costs them nothing. Otherwise fall right if x + h stays short of the next tree. That can block only the next tree, and this one counts in its place, so it is never worse than standing.

STEPS
  1. prev = −∞, the last occupied point
  2. If x − h > prev, fell it left; prev = x
  3. Else if it is the last tree, or x + h < the next x, fell it right; prev = x + h
  4. Else it stands; prev = x
BRUTEO(3ⁿ) trying left, right and standing for every tree
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<long long> x(n), h(n);
    for (int i = 0; i < n; i++) scanf("%lld %lld", &x[i], &h[i]);
    long long prev = LLONG_MIN;            // the last occupied point
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (x[i] - h[i] > prev) { cnt++; prev = x[i]; }             // fell it left
        else if (i == n - 1 || x[i] + h[i] < x[i + 1]) { cnt++; prev = x[i] + h[i]; }   // right
        else prev = x[i];                  // it stands
    }
    printf("%d\n", cnt);
}
TIMEO(n)one pass, the trees already sorted by x
SPACEO(1)the input arrays
TRAP

A segment that only touches the next tree. The segments are closed, so x + h equal to the next x covers that tree's point. The test is x + h < x[i + 1], and on the left x − h > prev, both strict.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
10 / DRILL UNIT 02 · Leave Room for What Comes Next · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Woodcutters with trees (x, h) = (1, 2), (2, 1), (5, 10), (10, 9), (19, 1)?

The first falls left to [−1, 1] and the second right to [2, 3]. The trees at 5 and 10 fit neither way, and the last falls right. With the last tree at 20 instead, 10 could fall right to [10, 19]: the second sample's 4.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
11 / MECHANISM UNIT 03 · REACH

ONE NUMBER: THE FURTHEST INDEX REACHED

A jump may stop short, so every index up to reach can be reached. Raise reach to i + nums[i] at each index. If i ever passes reach, nothing lands on i.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
12 / MECHANISM UNIT 03 · LEVELS

LEVELS OF REACH, LIKE A BREADTH-FIRST SEARCH

The indices first reached with k jumps form one block. end marks where the current block stops and far where the next one will. Reaching end costs one jump and moves end to far.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
13 / DRILL UNIT 03 · How Far Can You Reach · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

canJump([3, 2, 1, 0, 4])?

Indices 0 to 3 all reach exactly 3: 0 + 3, 1 + 2, 2 + 1 and 3 + 0. Index 4 is never reached.

DRILL 02 · RECALL

Why does jump stop reading at index n − 2?

If the last index closed a level, the loop would add a jump away from the goal. [0] would need 1 jump instead of 0.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
14 / PROBLEM #04 · REACH · MED

Jump Game

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

From index i you may jump up to nums[i] steps forward. Can you reach the last index from the first?

INTUITION

Every index up to reach can be reached, because a jump may stop short. So one number, the furthest index reached so far, says everything. Read left to right and raise it to i + nums[i]. If i ever passes reach, nothing before i lands on it, and nothing after it can be reached either.

STEPS
  1. reach = 0
  2. For each i: if i > reach, return false
  3. reach = max(reach, i + nums[i])
  4. Every index read, so return true
BRUTEO(n²) marking every index each reachable index can jump to
→
OPTIMALO(n)
↕ SCROLL
bool canJump(vector<int>& nums) {
    int reach = 0;                         // the furthest index reachable
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) return false;       // stranded before i
        reach = max(reach, i + nums[i]);
    }
    return true;
}
TIMEO(n)one pass
SPACEO(1)one counter
TRAP

Overwriting reach instead of taking the max. reach = i + nums[i] forgets a longer jump made earlier. On [3, 0, 0, 1] it shrinks reach to 1 at index 1 and answers false.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
15 / PROBLEM #05 · REACH · MED

Jump Game II

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

The same jumps, and the last index is always reachable. What is the fewest number of jumps?

INTUITION

Split the indices into levels: level k is every index that first becomes reachable with k jumps. It is breadth-first search, but each level is a contiguous block, so two numbers describe it. end is the last index of the current level, and far is the furthest any index in it jumps. When i reaches end, the level is done, one more jump is spent, and the next level ends at far.

STEPS
  1. jumps = 0, end = 0, far = 0
  2. For i from 0 to n − 2: far = max(far, i + nums[i])
  3. If i == end: jumps++ and end = far
  4. Return jumps
BRUTEO(n²) breadth-first search over every jump
→
OPTIMALO(n)
↕ SCROLL
int jump(vector<int>& nums) {
    int jumps = 0, end = 0, far = 0;       // end: the last index of this level
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        far = max(far, i + nums[i]);       // the next level reaches far
        if (i == end) {                    // this level is used up
            jumps++;
            end = far;
        }
    }
    return jumps;
}
TIMEO(n)one pass
SPACEO(1)three counters
TRAP

Reading the last index too. If the loop runs to n − 1 and the last index happens to close a level, it counts a jump away from the goal. [0] would take 1 jump instead of 0. Stop at n − 2.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
16 / DRILL UNIT 03 · How Far Can You Reach · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

jump([2, 3, 1, 1, 4])?

Level 1 is indices 1 and 2. Index 1 jumps as far as 4, the last index, so it is in level 2.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
17 / MECHANISM UNIT 04 · A DRY TANK MOVES THE START

A DRY TANK SKIPS EVERY START BEHIND IT

Drive from start and keep the tank. If it goes negative before i + 1, every start from start to i fails too, since each would arrive with less. Try i + 1, and trust the total at the end.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
18 / DRILL UNIT 04 · A Dry Tank Moves the Start

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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

g = −2, −2, −2, 3, 3. The tank goes negative at 0, 1 and 2, so start moves to 3. The total is 0, so start 3 works.

DRILL 02 · RECALL

The tank goes negative at i. Why skip every start between start and i?

Starting at start, the car reached each of them with a tank of 0 or more. Starting there instead means arriving with 0, which is no better, and it still fails at i.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
19 / PROBLEM #06 · REACH · MED

Gas Station

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

Stations on a circle: fill gas[i] at station i and burn cost[i] to reach the next. From which station can you go once round? The answer, if any, is unique.

INTUITION

If the total gas is at least the total cost, some start works; otherwise none does. To find it, drive from start and keep the tank. If the tank goes negative before i + 1, no start from start to i works. Each of them would arrive at i with no more gas than this run did. So the next start to try is i + 1, and one pass finds it.

STEPS
  1. total = 0, tank = 0, start = 0
  2. For each i: g = gas[i] − cost[i]; total += g; tank += g
  3. If tank < 0: start = i + 1 and tank = 0
  4. Return start if total ≥ 0, else −1
BRUTEO(n²) driving round from every start
→
OPTIMALO(n)
↕ SCROLL
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < (int)gas.size(); i++) {
        int g = gas[i] - cost[i];
        total += g;                        // the whole loop's balance
        tank += g;                         // the balance since start
        if (tank < 0) {                    // start..i cannot reach i + 1
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}
TIMEO(n)one pass round the circle
SPACEO(1)three counters
TRAP

Restarting at i instead of i + 1. Station i is the one the car could not leave with enough gas, so starting there fails too. The next candidate is i + 1.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
20 / MECHANISM UNIT 05 · CUT WHERE NOTHING COMES BACK

CUT WHERE NOTHING COMES BACK

Record each letter's last index. Reading left to right, the part must stretch to the last copy of every letter in it. When i reaches that end, cut, as early as the rule allows.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
21 / DRILL UNIT 05 · Cut Where Nothing Comes Back

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

partitionLabels("ababcbacadefegdehijhklij")?

The last a is at 8, so the first part is 0 to 8. Then the last e at 15 closes the second part, and the last j at 23 the third.

DRILL 02 · RECALL

Why does cutting as early as possible give the most parts?

Any valid cut can move left to the first point where nothing comes back. Waiting longer only glues together pieces that were free to separate.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
22 / PROBLEM #07 · BOUND · MED

Partition Labels

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

Cut a string into as many parts as possible so that each letter appears in one part only. Return the part sizes.

INTUITION

A part that holds a letter must reach that letter's last copy. So record each letter's last index first. Then read left to right, stretching end to the last index of every letter seen. When i reaches end, nothing inside the part appears later, and cutting there as early as possible leaves the most room for more parts.

STEPS
  1. last[c] = the last index of each letter
  2. start = 0, end = 0
  3. For each i: end = max(end, last[s[i]])
  4. If i == end: record end − start + 1 and start = i + 1
BRUTEO(2ⁿ · n) trying every set of cuts
→
OPTIMALO(n)
↕ SCROLL
vector<int> partitionLabels(string s) {
    int last[26] = {};
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
    vector<int> out;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i] - 'a']);  // this part must reach here
        if (i == end) {                    // nothing in it comes back
            out.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return out;
}
TIMEO(n)two passes
SPACEO(26)one last index per letter
TRAP

end = last[c] without the max. A letter whose last copy is near can pull end back inside a part that must reach further. On "abab" the second a pulls end back from 3 to 2, so "aba" is cut off and the two b's land in different parts.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
23 / MECHANISM UNIT 06 · A RANGE, NOT A COUNT

TRACK THE RANGE OF OPEN COUNTS

Each * could be three things, but the open counts it allows always form a range. Keep its ends, lo and hi. hi below 0 fails every reading; lo below 0 is clipped, since that reading has broken.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
24 / DRILL UNIT 06 · A Range, Not a Count · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

checkValidString("(*))")?

Read * as (: (()) balances. lo and hi both end at 0.

DRILL 02 · TRACE

checkValidString(")(*")?

The first ) has no ( before it in any reading, so hi drops to −1 at once.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
25 / DRILL UNIT 06 · A Range, Not a Count · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why is lo raised back to 0 when it goes negative?

A reading with more ) than ( so far can never recover. Dropping it leaves the readings still alive, whose fewest open count is 0.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
26 / PROBLEM #08 · BOUND · MED

Valid Parenthesis String

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

A string of (, ) and *, where each * may be (, ) or nothing. Can it be a balanced string?

INTUITION

With no stars, one count of open brackets decides it. With stars, the count could be several numbers at once, but always a whole range of them. So keep lo and hi, the fewest and the most open brackets possible. ( raises both, ) lowers both, and * lowers lo and raises hi. If hi drops below 0, every reading has a ) too many. A reading below 0 has already broken, so lo is raised back to 0. At the end, 0 must be in the range.

STEPS
  1. lo = 0, hi = 0
  2. ( : lo++, hi++; ) : lo−−, hi−−; * : lo−−, hi++
  3. If hi < 0, return false
  4. lo = max(lo, 0); at the end return lo == 0
BRUTEO(3ᵏ · n) trying every reading of the k stars
→
OPTIMALO(n)
↕ SCROLL
bool checkValidString(string s) {
    int lo = 0, hi = 0;                    // the fewest and most '(' open
    for (char c : s) {
        if (c == '(') { lo++; hi++; }
        else if (c == ')') { lo--; hi--; }
        else { lo--; hi++; }               // '*': ')', '(' or nothing
        if (hi < 0) return false;          // too many ')' in every reading
        lo = max(lo, 0);                   // a reading below 0 has broken
    }
    return lo == 0;
}
TIMEO(n)one pass
SPACEO(1)two counters
TRAP

Letting lo go negative. A negative lo stands for a reading with more ) than (, which can never recover. Without the clamp, "(*)" ends with lo = −1 and is rejected, though reading * as nothing balances it.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
27 / MECHANISM UNIT 07 · ONE PASS FROM EACH SIDE

ONE PASS PER NEIGHBOUR

Each child has a rule for the left neighbour and one for the right. Meet the left rules going right, then the right rules going left, keeping the larger need. Each count is the least allowed.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
28 / DRILL UNIT 07 · One Pass From Each Side · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

candy([1, 0, 2])?

[2, 1, 2]: both ends beat the 0 in the middle, which keeps 1.

DRILL 02 · TRACE

candy([1, 2, 2])?

[1, 2, 1]: the second 2 equals its left neighbour rather than beating it, so 1 is enough.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
29 / DRILL UNIT 07 · One Pass From Each Side · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why does the second pass take a max?

The count must satisfy both neighbours. Overwriting it with the right pass's need can drop below what the left neighbour requires.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
30 / PROBLEM #09 · BOUND · HARD

Candy

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

Children in a row, each with a rating. Everyone gets at least one candy, and a child rated higher than a neighbour gets more than that neighbour. The fewest candies in all?

INTUITION

Each child has two rules, one per neighbour, and they can be met separately. A left-to-right pass gives each child one more than its left neighbour when it is rated higher. A right-to-left pass does the same against the right neighbour, keeping the larger of the two needs. Every count is the least its rules allow, so the sum is the fewest.

STEPS
  1. c = [1, 1, …, 1]
  2. Left to right: if r[i] > r[i − 1], c[i] = c[i − 1] + 1
  3. Right to left: if r[i] > r[i + 1], c[i] = max(c[i], c[i + 1] + 1)
  4. Return the sum of c
BRUTEO(n²) raising counts until no rule is broken
→
OPTIMALO(n)
↕ SCROLL
int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> c(n, 1);                   // everyone gets one
    for (int i = 1; i < n; i++)            // beat the left neighbour
        if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--)       // beat the right one too
        if (ratings[i] > ratings[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
    return accumulate(c.begin(), c.end(), 0);
}
TIMEO(n)two passes
SPACEO(n)the candy array
TRAP

Dropping the max in the second pass. c[i] = c[i + 1] + 1 can lower a count the left pass needed. On [1, 2, 3, 1] it gives the 3 two candies, no more than the 2 beside it.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
31 / MECHANISM UNIT 08 · A LETTER THAT COMES BACK CAN WAIT

A LARGER LETTER THAT COMES BACK CAN WAIT

The answer is built as a stack. A larger letter on top steps aside for a smaller one only if a later copy can replace it. A letter that never comes back stays put.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
32 / DRILL UNIT 08 · A Letter That Comes Back Can Wait

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

removeDuplicateLetters("bcabc")?

a pops c and then b, since both appear again later. b and c are then pushed after it.

DRILL 02 · RECALL

When may the top of the stack be popped?

Larger alone is not enough: a letter that never comes back would be lost from the answer.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
33 / PROBLEM #10 · ORDER · MED

Remove Duplicate Letters

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

Remove duplicate letters so that each letter appears once, keeping the order of the rest, and return the result that is smallest in dictionary order.

INTUITION

Build the answer as a stack. Before pushing c, a larger letter on top may be popped if it appears again later, since that later copy can stand in for it after c. A letter with no later copy must stay, and a letter already on the stack is skipped. It is the monotonic stack, with one extra test.

STEPS
  1. last[c] = the last index of each letter
  2. Skip c if it is already on the stack
  3. While the top is larger than c and appears again after i, pop it
  4. Push c
BRUTEO(2ⁿ · n) trying every subsequence with each letter once
→
OPTIMALO(n)
↕ SCROLL
string removeDuplicateLetters(string s) {
    int last[128] = {};
    bool in[128] = {};                     // is it on the stack?
    for (int i = 0; i < (int)s.size(); i++) last[s[i]] = i;
    string st;                             // the answer, as a stack
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        if (in[c]) continue;               // already placed
        while (!st.empty() && st.back() > c && last[st.back()] > i) {
            in[st.back()] = false;         // it comes back later: let it wait
            st.pop_back();
        }
        st.push_back(c);
        in[c] = true;
    }
    return st;
}
TIMEO(n)each letter is pushed and popped at most once per copy
SPACEO(26)the stack and two tables of 26
TRAP

Popping a letter that never comes back. Without the last[top] > i test the stack is a plain monotonic stack, and on "cbacdcbc" the d is popped for the b and lost. The answer would be "abc", with no d at all.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
34 / MECHANISM UNIT 09 · THE ORDER A SWAP PROVES

SHORTEST FIRST, BECAUSE A SWAP SAYS SO

The deadlines add up to the same in any order, so only the finishing times matter. A task's duration delays itself and every task after it, so the shortest runs first.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
35 / DRILL UNIT 09 · The Order a Swap Proves · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Tasks and Deadlines with (a, d) = (6, 10), (8, 15), (5, 12)?

Shortest first: 5 ends at 5 (+7), 6 at 11 (−1), 8 at 19 (−4). 7 − 1 − 4 = 2.

DRILL 02 · RECALL

In Tasks and Deadlines, why do the deadlines not affect the best order?

The total is the sum of deadlines minus the sum of finishing times, and only the second sum depends on the order.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
36 / PROBLEM #11 · ORDER · MED

Tasks and Deadlines

MED order ▶ 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

Run all n tasks one after another; a task with deadline d finishing at f earns d − f, which may be negative. The largest total?

INTUITION

The total is (sum of deadlines) − (sum of finishing times), and the first sum does not depend on the order. A task's duration is paid in its own finishing time and in every later one. Swap two neighbours so the shorter runs first and the later finish stays put while the earlier one moves up. So run the shortest first.

STEPS
  1. Add up every deadline
  2. Sort the durations, the shortest first
  3. now += a for each task, and subtract now from the total
  4. Print the total, in 64 bits
BRUTEO(n! · n) trying every order
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<long long> a(n);
    long long total = 0;
    for (int i = 0; i < n; i++) { long long d; scanf("%lld %lld", &a[i], &d); total += d; }
    sort(a.begin(), a.end());              // the shortest first
    long long now = 0;
    for (int i = 0; i < n; i++) { now += a[i]; total -= now; }   // it finishes at now
    printf("%lld\n", total);
}
TIMEO(n log n)the sort
SPACEO(n)the durations
TRAP

Sorting by deadline. It feels like scheduling, but no task can be skipped, so the deadlines only add a constant. On (4, 9), (2, 4), (1, 7), (3, 6) the deadline order earns 3 and the shortest-first order earns 6. The sum of finishing times passes 2³¹ too, so keep it in 64 bits.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
37 / PROBLEM #12 · ORDER · MED

Job Sequencing Problem

MED order ▶ SOLVE ON GEEKSFORGEEKSGeeksforGeeks rates it Medium.
SIGNAL — WHAT GIVES IT AWAY

Jobs each take one unit of time and pay a profit only if finished by their deadline. Return how many jobs a most profitable schedule does, and its profit.

INTUITION

A set of jobs fits if, sorted by deadline, the kth job's deadline is at least k. So take jobs in deadline order and keep the profits taken in a min-heap. When the heap holds more jobs than the current deadline allows, the least profitable one is dropped: the one whose loss costs least. It is Heaps' take-it-back move with deadlines as the budget.

STEPS
  1. Sort the jobs by deadline
  2. Push each job's profit into a min-heap
  3. If the heap holds more than this deadline, pop the smallest
  4. Return [heap size, sum of the heap]
BRUTEO(2ⁿ · n log n) trying every set of jobs
→
OPTIMALO(n log n)
↕ SCROLL
vector<int> jobSequencing(vector<int> &deadline, vector<int> &profit) {
    int n = deadline.size();
    vector<pair<int, int> > jobs(n);
    for (int i = 0; i < n; i++) jobs[i] = make_pair(deadline[i], profit[i]);
    sort(jobs.begin(), jobs.end());        // by deadline
    priority_queue<int, vector<int>, greater<int> > kept;   // the smallest on top
    int total = 0;
    for (int i = 0; i < n; i++) {
        kept.push(jobs[i].second); total += jobs[i].second;
        if ((int)kept.size() > jobs[i].first) { total -= kept.top(); kept.pop(); }
    }
    return {(int)kept.size(), total};
}
TIMEO(n log n)the sort, then n heap moves
SPACEO(n)the jobs and the heap
TRAP

Taking the most profitable jobs first and never looking back. Sorted by profit, a job must go in the latest free slot up to its deadline, not the earliest. Putting it in the earliest blocks a job with a tighter deadline. The heap version avoids slots altogether.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
38 / DRILL UNIT 09 · The Order a Swap Proves · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

jobSequencing([4, 1, 1, 1], [20, 10, 40, 30])?

Three jobs share deadline 1 and only one fits, so the heap keeps the 40. The job with deadline 4 adds 20.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
39 / MECHANISM UNIT 10 · MEET AT THE MEDIAN

THE MIDDLE STICK BALANCES THE COST

Moving the target one unit costs 1 for each stick on one side and saves 1 on the other. At the median the two sides are equal, so no move helps.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
40 / DRILL UNIT 10 · Meet at the Median

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Stick Lengths on [2, 3, 1, 5, 2]?

Sorted, 1, 2, 2, 3, 5: the median is 2, and the gaps are 1 + 0 + 0 + 1 + 3.

DRILL 02 · RECALL

Why the median and not the mean?

Past the median, more sticks lie behind the target than ahead of it, so every further unit adds more cost than it removes.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
41 / PROBLEM #13 · ORDER · EASY

Stick Lengths

EASY order ▶ 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

Make every stick the same length; changing a length by x costs x. The least total cost?

INTUITION

Picture the target t sliding along the sorted lengths. Raising it by 1 costs 1 for every stick at or below it and saves 1 for every stick above. While fewer sticks are below than above, moving up pays. The two sides balance at the middle stick, so the median is the target, not the mean.

STEPS
  1. Sort the lengths
  2. m = p[n / 2], a median
  3. Add up |p[i] − m|
  4. Print the sum, in 64 bits
BRUTEO(n · range) trying every target length
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<long long> p(n);
    for (int i = 0; i < n; i++) scanf("%lld", &p[i]);
    sort(p.begin(), p.end());
    long long m = p[n / 2], cost = 0;      // a median
    for (int i = 0; i < n; i++) cost += llabs(p[i] - m);
    printf("%lld\n", cost);
}
TIMEO(n log n)the sort
SPACEO(n)the lengths
TRAP

The mean instead of the median. The mean minimises the sum of squared gaps, not of gaps. On 1, 2, 2, 2, 3, 9, 12 the mean, about 4.4, costs 23 and the median 2 costs 19. The cost can also pass 2³¹.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
42 / MECHANISM UNIT 11 · EVERYTHING UP TO REACH

EVERY SUM UP TO REACH

Sort the coins. If every sum to reach can be made, a coin up to reach + 1 extends that run by its own value. A larger coin leaves reach + 1 out for good.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
43 / DRILL UNIT 11 · Everything Up to Reach · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Missing Coin Sum on [1, 1, 3, 7]?

1, 1 and 3 cover 1 to 5. The next coin, 7, is larger than 6, so 6 can never be made.

DRILL 02 · RECALL

Why is reach + 1 the best number to patch in?

Any number up to reach + 1 extends the run, and a larger one extends it further. reach + 1 is the largest that leaves no gap.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
44 / PROBLEM #14 · COVER · MED

Missing Coin Sum

MED cover ▶ 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

Given coins, find the smallest sum that no subset of them adds up to.

INTUITION

Sort the coins and keep reach: every sum from 1 to reach can be made with the coins read so far. A next coin c ≤ reach + 1 extends that run, since each old sum plus c covers reach + 1 to reach + c. A coin c > reach + 1 leaves reach + 1 unmakeable for good, because every coin left is at least c.

STEPS
  1. Sort the coins
  2. reach = 0
  3. For each coin c: if c > reach + 1, stop; else reach += c
  4. Print reach + 1
BRUTEO(2ⁿ) listing every subset sum
→
OPTIMALO(n log n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; scanf("%d", &n);
    vector<long long> x(n);
    for (int i = 0; i < n; i++) scanf("%lld", &x[i]);
    sort(x.begin(), x.end());
    long long reach = 0;                   // every sum 1..reach can be made
    for (int i = 0; i < n; i++) {
        if (x[i] > reach + 1) break;       // reach + 1 can never be made
        reach += x[i];
    }
    printf("%lld\n", reach + 1);
}
TIMEO(n log n)the sort
SPACEO(n)the coins
TRAP

Reading the coins unsorted. A large coin read early stops the scan before the small coins that would have closed the gap. Unsorted, [2, 1] answers 1 instead of 4. reach also passes 2³¹, so keep it in 64 bits.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
45 / PROBLEM #15 · COVER · HARD

Patching Array

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

A sorted array and a number n. Add the fewest numbers so that every value from 1 to n is the sum of some subset.

INTUITION

Row 14's argument, used to build. With every sum up to reach covered, a next number at most reach + 1 extends the run for free. When the next number is too big, or there is none, reach + 1 must be added, and reach + 1 is the best number to add: it is the largest that still joins the run, so reach jumps to 2 · reach + 1.

STEPS
  1. reach = 0, i = 0, patches = 0
  2. While reach < n: if nums[i] ≤ reach + 1, reach += nums[i] and i++
  3. Otherwise patch: reach += reach + 1, patches++
  4. Return patches
BRUTEO(nᵏ) trying every set of k added numbers
→
OPTIMALO(m + log n)
↕ SCROLL
int minPatches(vector<int>& nums, int n) {
    long long reach = 0;                   // every sum 1..reach can be made
    int i = 0, patches = 0;
    while (reach < n) {
        if (i < (int)nums.size() && nums[i] <= reach + 1) reach += nums[i++];
        else { reach += reach + 1; patches++; }   // add reach + 1, the best patch
    }
    return patches;
}
TIMEO(m + log n)each number read once, and each patch doubles reach
SPACEO(1)three counters
TRAP

reach in 32 bits. n can be 2³¹ − 1, and reach can pass it on the last step, so reach < n overflows and loops for ever. Keep reach in 64 bits.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
46 / DRILL UNIT 11 · Everything Up to Reach · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

minPatches([1, 3], 6)?

1 covers 1. 3 is larger than 2, so patch in 2: reach is 3. Then 3 extends reach to 6.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
47 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

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

TWO WAYS TO PAY OR PLACE, AND BOTH WORK NOW

take the one that leaves the more useful resources

KEEP THE OPTIONSO(n)
PLACE ITEMS ALONG A LINE WITH NO OVERLAP

go left to right and take the leftmost legal spot

LEAVE ROOMO(n)
CAN YOU REACH THE END, OR IN HOW FEW JUMPS?

carry the furthest index, or levels of it

REACHO(n)
A CIRCULAR TRIP WITH GAINS AND COSTS

a negative running balance moves the start past it

DRY TANKO(n)
SPLIT SO EACH LETTER IS IN ONE PART

stretch to each letter's last index, then cut

LAST OCCURRENCEO(n)
A WILDCARD THAT COULD BE SEVERAL THINGS

keep the range of possible counts, not every reading

RANGE OF COUNTSO(n)
A RULE FOR BOTH NEIGHBOURS OF EVERY ITEM

one pass per side, the larger need wins

TWO PASSESO(n)
SMALLEST IN DICTIONARY ORDER, KEEPING ONE OF EACH

a stack where a letter that comes back may wait

STACK THAT WAITSO(n)
CHOOSE AN ORDER FOR ALL ITEMS, OR WHICH ONES FIT

sort by the key that swapping two neighbours proves

EXCHANGE ARGUMENTO(n log n)
MAKE EVERY VALUE EQUAL AT LEAST COST

meet at the median

MEDIANO(n log n)
WHICH SUMS CAN SOME COINS MAKE?

sorted, every sum up to reach is covered

UP TO REACHO(n log n)
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
48 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Assign cookies to children so the most are content; a child needs a cookie at least their greed. Which move?

Sort both, then give each child the smallest cookie that satisfies them. Swapping a larger cookie to a less greedy child never helps. It is Assign Cookies (dp-2).

DRILL 02 · TRANSFER

Minimum Number of Taps to Open to Water a Garden: each tap waters [i − r, i + r]. Which move?

For each left end keep the furthest right end any tap starting there covers. Then it is Jump Game II: levels of reach, one tap per level.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
49 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Arrange numbers to form the largest number when written side by side. Which move?

Put a before b when a + b beats b + a as strings. Swapping two neighbours that break that rule makes the number larger. It is Largest Number (sorting).

DRILL 02 · RECALL

What does a greedy solution need before it can be trusted?

Taking the best-looking option is often wrong. A greedy solution is right only when some argument shows the choice loses nothing: it stays ahead, or a swap into any other answer costs nothing.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
50 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

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

A CHOICE THAT LOOKS BEST BUT IS NOT SAFE

Greedy fails silently. Before coding, find the argument: the choice leaves at least as much for later, or swapping it into any other answer costs nothing. Without one, test it on a brute force.

SORTING BY THE WRONG KEY

Tasks and Deadlines sorts by duration, not deadline, and Stick Lengths meets at the median, not the mean. The key comes from the swap argument, not from what the statement mentions first.

TOUCHING COUNTED AS FREE

Woodcutters' segments are closed, so a tree may not end on the next tree's point. Strict and non-strict comparisons decide many greedy problems.

RESTARTING ONE STEP TOO EARLY

When the tank goes dry at i, starting at i fails too. The next start to try is i + 1.

A SECOND PASS THAT UNDOES THE FIRST

Candy's right-to-left pass must keep the larger of the two needs. Overwriting the count loses what the left neighbour required.

OVERFLOW IN A RUNNING SUM

Finishing times, stick costs, coin reach and Patching Array's reach all pass 2³¹ on large inputs. Keep them in 64-bit integers.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
51 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

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

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Keep the options
O(n)
O(1)
of two choices that work, spend the less useful resource
Leave room
O(n)
O(1)
fall left if it fits, right if it fits, else stand
Reach
O(n)
O(1)
reach = max(reach, i + nums[i]); fail when i > reach
Levels of reach
O(n)
O(1)
at i == end: one more jump, end = far
Dry tank
O(n)
O(1)
tank < 0 at i: start = i + 1; answer only if total ≥ 0
Last occurrence
O(n)
O(26)
end = max(end, last[c]); cut at i == end
Range of counts
O(n)
O(1)
( and ) move lo and hi together; * spreads them
Two passes
O(n)
O(n)
left pass, then right pass with max
Stack that waits
O(n)
O(26)
pop a larger top only if it comes back
Exchange argument
O(n log n)
O(n)
sort by the key a neighbour swap proves
Up to reach
O(n log n)
O(1)
c ≤ reach + 1 extends; else reach + 1 is missing
INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
52 / CLOSE MODULE 21 · GREEDY

TAKE IT NOW

The 10 was spent and the 5 kept; trees fell left while the left was free; reach and levels of reach replaced every path; a dry tank moved the start past it; a part stretched to each letter's last copy; two numbers held every reading of the stars; one pass per neighbour paid the candies; a letter that comes back waited; the shortest task ran first; the sticks met at the median; and every sum up to reach was covered. Assign Cookies (dp-2) and Largest Number (sorting) are unit 9's swap argument, and the interval greedies sort by end in Intervals and Sweep.

00%
OF THIS DECK SOLVED
← ALL TOPICS← HEAPSMONOTONIC STACK & DEQUE →

Module 21. Fifteen problems: ten on LeetCode, three on CSES, one on Codeforces and one on GeeksforGeeks. Next in the sheet: intervals and sweep.

INVARIANT · GREEDY · ONE CHOICE, NEVER UNDONE · GREEDY
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 21 · GREEDY

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.