INVARIANT · ARRAYS · ONE PASS · TWO INDICES
01
00/18
01 / COVER STEP 03 · ARRAYS
INVARIANT · STEP 03 · DECK 1 OF 2
18 PROBLEMS 9 IDEAS

18 original problems, 14 visual lessons, and guided practice for merging and prefix/suffix products. Explain the idea, predict the next move, then code without looking.

18Problems
9Patterns
14Units
14Visual lessons
← → ↑ ↓  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 · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 18 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.

ARRAYS [EASY] · 06
ARRAYS [MEDIUM] · 12
SOLVED HAS A LEETCODE LINK
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
03 / MECHANISM UNIT 01 · DEDUPE · CODE MIRRORED

Keep one copy

r reads; w marks the next free slot. Keep the unique values in the prefix before w.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
04 / DRILL UNIT 01 · The Write Pointer · 1 OF 2

Quick check

DRILL 01 · RECALL

What does a[w-1] hold when we check a[r]?

It holds the last value we kept. The array is sorted, so if the current value is different, we keep it next.

DRILL 02 · TRACE

Run the loop on [1, 1, 2, 2, 2, 3]. Just before checking the final 3, what are w and the array?

w = 2 because we have kept 1 and 2. The array is [1, 2, 2, 2, 2, 3]. Only the first two slots are part of the answer so far. The loop has yet to check the final 3.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
05 / DRILL UNIT 01 · The Write Pointer · 2 OF 2

Quick check

DRILL 01 · BUG

This code works on [1,2,3]. What needs to change for it to handle duplicates?

int w = 1;
for (int r = 1; r < n; r++)
    if (a[r] != a[w - 1])
        a[w] = a[r]; w++;        // commit
return w;

Put { after the if condition and } after w++. Now the code copies the value and increases w only when it keeps a new value. On [1,1,2], it returns 2 instead of 3.

DRILL 02 · TRANSFER

Keep at most two copies of each value in a sorted array. Return n if n ≤ 2. How should the loop start and what should it compare?

Start r and w at 2. If a[r] matches a[w-2], we already kept two copies. Otherwise, keep it.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
06 / PROBLEM #01 · WRITE-POINTER · EASY

Remove Duplicates from Sorted Array

EASY write-pointer ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Sorted input; keep one copy of each value in place.

INTUITION

The prefix before w holds the unique values kept so far. Scan with r; write only when a value differs from the last keeper.

STEPS
  1. a[0] is a keeper by definition — nothing precedes it — so start w at 1
  2. Walk r from 1 to n−1, reading every element exactly once
  3. Compare a[r] against a[w−1], the LAST COMMITTED value, never against a[r−1]
  4. When they differ, write a[w] = a[r] and advance w
  5. When they match, advance r alone; w holding still is what drops the duplicate
  6. Return w — it counted the keepers, so it IS the new length
BRUTEO(n log n)
→
OPTIMALO(n)
↕ SCROLL
// Two indices, one array. r reads everything; w commits only keepers.
// The invariant w <= r is what makes writing in place safe: the slot w
// overwrites was already read by r, so no unread data can be destroyed.
int removeDuplicates(vector<int>& a) {
    if (a.empty()) return 0;
    int w = 1;                          // a[0] is a keeper by definition

    for (int r = 1; r < a.size(); r++)
        if (a[r] != a[w - 1])           // differs from the LAST KEPT value?
            a[w++] = a[r];              // commit it, then widen the answer

    return w;                           // w counted keepers, so it IS the length
}
TIMEO(n)each element is read once and written at most once
SPACEO(1)two integer indices — nothing allocated at all
TRAP

Return the kept length. Values beyond that prefix do not matter.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / THE WRITE POINTER ARRAYS I · VISUAL LESSON
STEP 1 / 6

Keep the first part. Return its length.

The input is sorted. Put one copy of each value at the front, in place.

 20
 21
 52
 53
 94
↓
 20
 51
 92
 ·3
 ·4

Return 3. Only the first three slots count; the tail does not need clearing.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
07 / MECHANISM UNIT 02 · REVERSE · CODE MIRRORED

Rotate with three reversals

For a right rotation: reverse everything, reverse the first k values, then reverse the rest. Reduce k modulo n first.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
08 / MECHANISM UNIT 02 · MOVEZERO · CODE MIRRORED

Keep the non-zeros in order

Swap each non-zero into the next prefix slot. Advance w only for a non-zero; the displaced zero moves behind the kept prefix.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
09 / DRILL UNIT 02 · Compaction & Rotation · 1 OF 2

Quick check

DRILL 01 · RECALL

When rotating right with three reversals, what does the first reversal do?

It moves the last k values to the front and the other values to the back. Both groups are now backwards. Reverse each group to put its values back in order.

DRILL 02 · TRACE

Rotate [1,2,3,4,5,6,7] right by 10. What goes wrong if you skip k %= n?

begin() + 10 goes beyond the array. With k %= n, 10 becomes 3 and the result is [5,6,7,1,2,3,4].

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
10 / DRILL UNIT 02 · Compaction & Rotation · 2 OF 2

Quick check

DRILL 01 · BUG

This code tries to move zeros to the end by swapping from the back. What rule can it break?

int w = 0, r = a.size() - 1;
while (w < r) {
    if (a[w] == 0)
        swap(a[w], a[r--]);   // pull a value from the back
    else w++;
}

Swapping from the back can change the order of the nonzero values. For example, 12 can move ahead of 1. Move Zeroes asks us to keep their original order.

DRILL 02 · TRANSFER

In Move Zeroes, why does the loop swap a[w] and a[r] instead of just copying a[r] to a[w]?

The swap puts the nonzero value in the next slot and moves the displaced zero back. Copying alone can leave extra copies of values. Copying works if you also fill the remaining slots with zeros at the end.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
11 / PROBLEM #03 · WRITE-POINTER · EASY

Move Zeroes

EASY write-pointer ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Move zeros to the end while preserving non-zero order.

INTUITION

Write each non-zero value into the next free slot, then fill the remaining suffix with zeros. The write pointer never destroys unread input.

STEPS
  1. Set w = 0 — the next slot a non-zero value is owed
  2. Walk r across the whole array, reading every element once
  3. When a[r] is zero, do nothing: w stays, so the slot remains owed
  4. When a[r] is non-zero, swap a[w] and a[r], then advance w
  5. Order is preserved because non-zeros are written in the order they were read
  6. When r reaches the end every non-zero is packed and the zeros have all drifted back
BRUTEO(n) time · O(n) space
→
OPTIMALO(n)
↕ SCROLL
// The write pointer again, but SWAPPING because every element must
// survive: the zero displaced from w travels to r, which is already read.
void moveZeroes(vector<int>& a) {
    int w = 0;                              // oldest slot still owed a non-zero

    for (int r = 0; r < a.size(); r++)
        if (a[r] != 0)
            swap(a[w++], a[r]);             // order kept: written as they were read
}
TIMEO(n)one pass; each element is read once and swapped at most once
SPACEO(1)two integer indices — nothing allocated
TRAP

Keep the non-zero values in their original order; arbitrary swaps can break stability.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
12 / PROBLEM #02 · INDEX-ALGEBRA · EASY

Rotate Array

EASY index-algebra ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Rotate right by k without an extra array.

INTUITION

Reduce k modulo n. Reverse the whole array, then the first k values and the rest to restore their order.

STEPS
  1. Take k %= n first — k may exceed n, and a[begin() + k] past the end is undefined
  2. Reverse the entire array: the blocks are now on the correct sides, both backwards
  3. Reverse the first k elements to un-reverse the block that moved to the front
  4. Reverse the remaining n−k to un-reverse the other one
  5. Every element was touched exactly twice, so this is O(n) with no allocation
BRUTEO(n·k)
→
OPTIMALO(n)
↕ SCROLL
// Reversal rotation. The first reversal puts the right BLOCKS in the
// right places; the other two fix the order inside each block.
void rotate(vector<int>& a, int k) {
    int n = a.size();
    k %= n;                                 // k may exceed n - this is in the tests

    reverse(a.begin(), a.end());            // 1. blocks swap sides, both backwards
    reverse(a.begin(), a.begin() + k);      // 2. fix the block now at the front
    reverse(a.begin() + k, a.end());        // 3. fix the block now at the back
}
TIMEO(n)three reversals over n elements — each element moves exactly twice
SPACEO(1)one temporary per swap; no auxiliary array
TRAP

Use k %= n. For a generalized empty-array input, return before taking modulo.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / COMPACTION & ROTATION ARRAYS I · VISUAL LESSON
STEP 1 / 6

Keep order while moving zeros.

Move every non-zero value forward without changing its relative order.

 00
 41
 02
 23
 74
↓
 40
 21
 72
 03
 04

A temporary list works in O(n) space. A write pointer builds the same non-zero prefix inside the input.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
13 / BUILD THE IDEA ARRAYS I · LEARN → TRY

STEP 1 / 4

Merge without losing values

Two sorted arrays. The first has spare slots at the end.

 20
 51
 82
 ·3
 ·4
 ·5
 10
 31
 92

Merge into the first array. The dots are spare slots, not values. A temporary result is a valid starting approach.

Use the deck arrows to continue or skip.
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
14 / INDEPENDENT PRACTICE NO METHOD GIVEN

Your turn: change the rule

A sorted array may keep at most two copies of each value. Change it in place and return the kept length. Try [1,1,1,2,2,3].

Write and run your code in your editor or the judge. Explain why it works.

Remove Duplicates II ↗
Need a hint?

The next kept value must not become a third copy. What would you compare it with?

Check your reasoning

Return 5; the first five values are [1,1,2,2,3]. A write pointer can keep a value if fewer than two were kept, or if it differs from a[w−2]. A carefully maintained run counter also works. O(n) time, O(1) space.

Self-reported; saved on this browser only. Not a judge result.

Next session: try again without the hint. Later this week: solve it among other topics. If you needed help, explain the missing idea before retrying.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
15 / MECHANISM UNIT 03 · XOR · CODE MIRRORED

Let pairs cancel

x XOR x = 0. Fold the values and watch the unpaired value survive. The pairing assumption matters.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
16 / DRILL UNIT 03 · XOR & The Sum Identity · 1 OF 2

Quick check

DRILL 01 · RECALL

In Single Number, every value appears twice except one. Why does XOR work even when the matching values are far apart?

XOR can be grouped and reordered. Equal values cancel, so a ^ b ^ a = 0 ^ b = b.

DRILL 02 · TRACE

For Missing Number on [3,0,1], what does the sum method compute? What can go wrong with large inputs?

The expected sum is 6 and the actual sum is 4, so 2 is missing. A large sum can exceed what a 32-bit integer can store. Use a wider type for the sum or use XOR.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
17 / DRILL UNIT 03 · XOR & The Sum Identity · 2 OF 2

Quick check

DRILL 01 · BUG

This code returns 4 on [1,1,0,1,1,1], but the longest run is 3. What causes the extra 1?

int run = 0, best = 0;
for (int v : a) {
    if (v == 1) run++;
    else run = 0;
    best = max(best, run + 1);
}

The counter already includes the current 1. Remove the extra + 1 when updating best.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
18 / PROBLEM #04 · XOR-IDENTITY · EASY

Missing Number

EASY xor-identity ▶ SOLVE ON LEETCODEReturns in Bit Manipulation, solved by XOR-ing indices against values instead of by the sum identity.
SIGNAL — WHAT GIVES IT AWAY

Exactly one value is missing from 0 through n.

INTUITION

Subtract the actual sum from n(n+1)/2, or XOR all values with all indices and n. The complete range cancels except for the missing value.

STEPS
  1. Note that indices 0..n and values 0..n differ by exactly one missing element
  2. Fold every index i from 0 to n into an accumulator x
  3. Fold every array element into the same x
  4. Every present value has now been XOR-ed exactly twice and cancelled to 0
  5. x holds the one value that was folded once — the missing number
  6. Alternative: n(n+1)/2 minus the actual sum, but watch the overflow
BRUTEO(n log n)
→
OPTIMALO(n)
↕ SCROLL
// XOR the full range against what is actually present. Every value
// that IS there gets folded twice and cancels; the hole is folded once.
// Preferred over n(n+1)/2 because no intermediate can ever overflow.
int missingNumber(vector<int>& a) {
    int n = a.size(), x = 0;

    for (int i = 0; i < n; i++)
        x ^= i ^ a[i];                      // index and value, both folded
    return x ^ n;                           // index n has no element to pair with
}
TIMEO(n)a single fold over indices and values
SPACEO(1)one accumulator, which never grows past the largest element
TRAP

Promote to a wider type before multiplying n*(n+1); casting after multiplication is too late.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
19 / PROBLEM #05 · COUNTER · EASY

Max Consecutive Ones

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

Find the longest uninterrupted run of ones.

INTUITION

Increment run on a one; reset it on a zero. Track best separately so an earlier run is not lost.

STEPS
  1. Keep two integers: run (the current streak) and best (the largest seen)
  2. For each value, if it is 1 then run++, otherwise run = 0
  3. Update best = max(best, run) on EVERY element, not only when the run breaks
  4. Return best — a run of length 0 is correct for an array with no 1s
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
// The seed of Kadane: a running quantity and a best-so-far.
// best is updated on EVERY element, so a streak that runs to the end
// of the array is still recorded.
int findMaxConsecutiveOnes(vector<int>& a) {
    int run = 0, best = 0;

    for (int v : a) {
        run = (v == 1) ? run + 1 : 0;       // a 0 ends the streak entirely
        best = max(best, run);              // record here, not at the break
    }
    return best;
}
TIMEO(n)one pass, one comparison per element
SPACEO(1)two integers
TRAP

A zero resets run to 0. Count consecutive ones, not the total number of ones.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
20 / PROBLEM #06 · XOR-IDENTITY · EASY

Single Number

EASY xor-identity ▶ SOLVE ON LEETCODEReturns in Bit Manipulation, where the XOR identity that makes this work is the lesson rather than a trick.
SIGNAL — WHAT GIVES IT AWAY

Every value occurs twice except one.

INTUITION

XOR is associative, x XOR x is zero, and x XOR zero is x. Folding the array cancels every pair.

STEPS
  1. Start an accumulator at 0 — XOR's identity, so 0 ^ v is always v
  2. Fold every element into it with x ^= v
  3. Each paired value cancels itself: v ^ v is 0, wherever the two sit
  4. Order never mattered, because XOR is commutative and associative
  5. Return x — the only value folded an odd number of times
BRUTEO(n) time · O(n) space
→
OPTIMALO(n)
↕ SCROLL
// XOR is parity per bit column. A value appearing twice contributes
// an even number of 1s to every column, so it contributes nothing at all.
// Order is irrelevant: XOR is commutative AND associative.
int singleNumber(vector<int>& a) {
    int x = 0;                              // 0 is XOR's identity

    for (int v : a)
        x ^= v;                             // equal pairs cancel to 0
    return x;                               // only the loner survives
}
TIMEO(n)one fold over the array
SPACEO(1)one accumulator, no map and no sort
TRAP

The pairing assumption is essential. XOR does not solve arbitrary frequency counts.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / XOR & THE SUM IDENTITY ARRAYS I · VISUAL LESSON
STEP 1 / 6

Pairs disappear under XOR.

For Single Number, every value appears twice except one. Order does not matter.

6 ⊕ 3 ⊕ 6 = (6 ⊕ 6) ⊕ 3 = 3

x ⊕ x = 0 and 0 ⊕ x = x. Associativity and commutativity let us group matching values without sorting.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
21 / MECHANISM UNIT 04 · HASH · CODE MIRRORED

Remember the missing partner

Before storing x, look for target - x among earlier values. The map remembers their indices.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
22 / DRILL UNIT 04 · The Hashmap Complement · 1 OF 2

Quick check

DRILL 01 · RECALL

In Two Sum, why do we look for t - a[i] before adding a[i] to the map?

Adding first can pair the current value with itself. For [3,5] and target 6, it could return [0,0]. Looking first limits the search to earlier indices.

DRILL 02 · TRACE

Run Two Sum on [2,7,11,15,3,6] with target 21. At which index does it find a match, and which earlier value does it find?

At index 5, the value is 6 and it needs 15. The map already holds 15 at index 3, so the result is [3,5].

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
23 / DRILL UNIT 04 · The Hashmap Complement · 2 OF 2

Quick check

DRILL 01 · TRANSFER

The array is already sorted. How can you find the pair in one pass using constant extra space?

Start one pointer at each end. If the sum is too small, move the left pointer right. If it is too large, move the right pointer left. This takes O(n) time and O(1) extra space.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
24 / PROBLEM #07 · HASHING · MED

Two Sum

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

Return two different indices whose values sum to the target.

INTUITION

For each x, look for target-x among earlier values. If absent, store x and its index for later elements.

STEPS
  1. Create an empty map from value to the index where it was seen
  2. Walk i across the array once
  3. Compute need = t − a[i], the only partner that can work for this element
  4. If need is already in the map, return {map[need], i} — done
  5. Otherwise store a[i] → i and continue
  6. Check BEFORE storing, or an element whose double is t will pair with itself
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
// The reframe: "do two values sum to t" is a question about PAIRS.
// "Have I seen t - a[i]" is a question about ONE value, and a map answers
// that in O(1). Check BEFORE storing, or a[i] pairs with itself.
vector<int> twoSum(vector<int>& a, int t) {
    unordered_map<int, int> seen;           // value -> index it was seen at

    for (int i = 0; i < a.size(); i++) {
        int need = t - a[i];                // the ONE partner that works
        if (seen.count(need))               // has it already gone past?
            return {seen[need], i};
        seen[a[i]] = i;                     // store AFTER checking
    }
    return {};
}
TIMEO(n)one pass with O(1) expected lookup per element
SPACEO(n)the map holds at most n entries — this is the trade being made
TRAP

Look up before inserting, or an element may incorrectly pair with itself.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / THE HASHMAP COMPLEMENT ARRAYS I · VISUAL LESSON
STEP 1 / 5

Search for the missing partner.

For target 10 and current value 7, the needed earlier value is 3.

earlier value = target − current value

Checking every pair costs O(n²). A map looks up an earlier value by its key. New to sets/maps? Try Contains Duplicate first; otherwise skip it.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
25 / MECHANISM UNIT 10 · RUNS · CODE MIRRORED

Walk only from the start

Start at x only when x-1 is absent. Each distinct value is then visited in one consecutive run.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
26 / DRILL UNIT 10 · Longest Consecutive Run · 1 OF 2

Quick check

DRILL 01 · RECALL

Longest Consecutive has a loop inside a loop. Why is the total time expected to be O(n)?

We start a walk at x only if x-1 is missing from the set. Each distinct value is visited by one walk. With expected constant-time set lookups, the total work is expected O(n).

DRILL 02 · TRACE

On [100,4,200,1,3,2], which values start a run of consecutive numbers?

100, 200, and 1 start runs because 99, 199, and 0 are missing. The run starting at 1 is [1,2,3,4] and has length 4.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
27 / DRILL UNIT 10 · Longest Consecutive Run · 2 OF 2

Quick check

DRILL 01 · TRANSFER

Why doesn’t Kadane’s algorithm solve Longest Consecutive Sequence?

Kadane works with elements next to each other in the array. In Longest Consecutive, values such as 2, 3, and 4 can appear anywhere in the array.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
28 / PROBLEM #14 · HASHING · MED

Longest Consecutive Sequence

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

Consecutive values can appear anywhere; input order is irrelevant.

INTUITION

Put values in a set. Start a walk at x only when x-1 is absent; then count x,x+1,... . Each unique value belongs to one walk.

STEPS
  1. Insert every value into a hash set — this also removes duplicates for free
  2. Iterate over the values
  3. Skip immediately if v−1 is in the set: something else is the head of this run
  4. Otherwise walk v+1, v+2, … while each is present, counting the length
  5. Track the maximum length seen
  6. Total walking is bounded by n, because no run is ever walked twice
BRUTEO(n log n)
→
OPTIMALO(n)
↕ SCROLL
// A while inside a for, and still O(n) -- because of ONE guard.
// Only a value with no left neighbour starts a walk, so every run is
// traversed exactly once across the whole execution. Drop the guard and
// the identical code becomes O(n^2).
int longestConsecutive(vector<int>& a) {
    unordered_set<int> s(a.begin(), a.end());       // dedupes for free
    int best = 0;

    for (int v : s) {
        if (s.count(v - 1)) continue;               // not a head - skip
        int x = v, len = 1;
        while (s.count(x + 1)) { x++; len++; }      // walk the run once
        best = max(best, len);
    }
    return best;
}
TIMEO(n)each run walked exactly once; the guard is what makes this linear
SPACEO(n)the hash set holds every distinct value
TRAP

Iterate distinct values and start only at run boundaries. Restarting from every value can become quadratic.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / LONGEST CONSECUTIVE RUN ARRAYS I · VISUAL LESSON
STEP 1 / 5

Consecutive values need not be adjacent.

For [9,4,2,3,2,10], the longest consecutive sequence is 2,3,4.

INPUT POSITIONS
9 · 4 · 2 · 3 · 2 · 10
VALUE RUNS
2 → 3 → 4
9 → 10

Sorting and scanning works in O(n log n), skipping duplicates. A hash set supports expected O(n) time without sorting.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
29 / BUILD THE IDEA ARRAYS I · LEARN → TRY

STEP 1 / 3

Add once. Reuse the totals.

A prefix is the first part of an array. P[i] is the sum of the first i values.

i01234
a[i]3-142—
P[i]03268

Start P[0]=0. To add one more value: P[i+1]=P[i]+a[i]. The extra zero makes ranges starting at index 0 work too.

Use the deck arrows to continue or skip.
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
30 / BUILD THE IDEA ARRAYS I · LEARN → TRY

STEP 1 / 4

Use everything except this value

For [2,3,4,5], the answer at index 1 is 2 × 4 × 5 = 40.

 20
 31
 42
 53
answer[i] = product before i × product after i

A fresh loop for every index takes O(n²). Division is not allowed. A suffix is the last part of an array.

Use the deck arrows to continue or skip.
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
31 / MECHANISM UNIT 14 · PREFIX · CODE MIRRORED

Count earlier matching prefixes

A subarray sums to k when its boundary prefixes differ by k. Seed {0:1}; query before recording the current prefix.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
32 / DRILL UNIT 14 · Prefix Sums + Hashmap · 1 OF 2

Quick check

DRILL 01 · RECALL

Why start the prefix-sum map with {0: 1}?

There is one prefix of sum 0 before the first element. It lets us count a subarray starting at index 0 whenever the running sum reaches k.

DRILL 02 · TRACE

On [3,4,7,2,-3,1,4,2], how many subarrays sum to 7? Can the usual shrinking window find them all?

There are 4: [3,4], [7], [7,2,-3,1], and [1,4,2]. Adding a negative can lower the sum, so shrinking whenever the sum exceeds 7 can miss a match.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
33 / DRILL UNIT 14 · Prefix Sums + Hashmap · 2 OF 2

Quick check

DRILL 01 · TRANSFER

We have a method to count subarrays with sum k. What changes if we want the longest such subarray, or a count using XOR?

For the longest subarray, store the first index of each prefix sum and track the largest distance. For an XOR count, store frequencies of running XOR values and look for prefixXor ^ k.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
34 / PROBLEM #18 · HASHING · MED

Subarray Sum Equals K

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

Count contiguous subarrays summing to k; negative values are allowed.

INTUITION

If the current prefix is s, every earlier prefix s-k starts a valid subarray. Store prefix frequencies, seeded with one empty prefix of sum zero.

STEPS
  1. Keep a running prefix sum and a map from prefix value to how many times it occurred
  2. Seed the map with {0: 1} — the empty prefix, which closes subarrays starting at index 0
  3. At each element, add it to the running sum
  4. Add map[sum − k] to the answer: every earlier equal-difference prefix is a hit
  5. Then increment map[sum], recording this prefix for later elements
  6. Check before recording, exactly as Two Sum checks the complement before storing
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
// Two Sum on prefix sums: a[j+1..i] sums to k iff P(j) = P(i) - k.
// The map counts prefix OCCURRENCES because we are counting subarrays,
// and it is seeded with {0:1} for the empty prefix. Negatives are handled
// for free -- which is exactly why a sliding window will not do.
int subarraySum(vector<int>& a, int k) {
    unordered_map<int, int> cnt{{0, 1}};    // the empty prefix counts
    int sum = 0, total = 0;

    for (int v : a) {
        sum += v;
        total += cnt[sum - k];              // every earlier P(j)=sum-k closes one
        cnt[sum]++;                         // record AFTER checking
    }
    return total;
}
TIMEO(n)one pass with O(1) expected map operations
SPACEO(n)the map holds at most n distinct prefix sums
TRAP

Query before recording the current prefix. Ordinary shrinking windows fail with negatives; zeros also require careful counting.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / PREFIX SUMS + HASHMAP ARRAYS I · VISUAL LESSON
STEP 1 / 7

A range is a difference of two totals.

For [3,−1,4,2], the totals before each boundary are [0,3,2,6,8].

sum of indices 1 through 2 = 6 − 3 = 3

A prefix is the first part of the array. Subtract the total before the range from the total just after it. The prefix bridge in the main deck lets you practise this first.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
35 / INDEPENDENT PRACTICE NO METHOD GIVEN

Your turn: a different question

Given integers, including negatives, return the length of the longest non-empty subarray with sum k; return 0 if none exists. Try [1,−1,5,−2,3], k=3.

Write and run your code in your editor or the judge. Explain why it works.

Need a hint?

Which earlier boundary gives the greatest distance to the current boundary?

Check your reasoning

Answer 4: [1,−1,5,−2]. Save the earliest index of each prefix sum, starting with sum 0 at index −1. For current sum s at i, look for s−k. Keep the largest distance. Never overwrite an earlier index. Test [0,0], k=0 → 2; [2], k=3 → 0. Expected O(n) time, O(n) space.

Self-reported; saved on this browser only. Not a judge result.

Next session: try again without the hint. Later this week: solve it among other topics. If you needed help, explain the missing idea before retrying.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
36 / MECHANISM UNIT 05 · DUTCH · CODE MIRRORED

Shrink the unknown region

Zeros sit before low; ones before mid; twos after high. After moving a 2, inspect the incoming value.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
37 / DRILL UNIT 05 · Dutch National Flag · 1 OF 2

Quick check

DRILL 01 · RECALL

When a[mid] == 2, we swap it with a[high] and decrease high. Why does mid stay put?

The value that came from high has yet to be checked. Moving mid now would skip it.

DRILL 02 · TRACE

Start with [2,0,1], low = mid = 0, and high = 2. What does the first step do?

Swap the 2 at index 0 with the 1 at index 2. The array becomes [1,0,2] and high drops to 1. Keep mid at 0 so the next step checks the 1.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
38 / DRILL UNIT 05 · Dutch National Flag · 2 OF 2

Quick check

DRILL 01 · BUG

What does the loop skip if its condition is mid < high?

while (mid < high) {
    if (a[mid] == 0) swap(a[low++], a[mid++]);
    else if (a[mid] == 1) mid++;
    else swap(a[mid], a[high--]);
}

When mid == high, one slot still needs to be checked. Use mid <= high. With the wrong condition, [1,0] stays unsorted.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
39 / PROBLEM #08 · PARTITION · MED

Sort Colors

MED partition ▶ SOLVE ON LEETCODEReturns in Sorting as the Dutch national flag partition — the same three-region pass, framed as a sorting primitive.
SIGNAL — WHAT GIVES IT AWAY

The array contains only 0, 1 and 2; partition it in place.

INTUITION

Keep zeros before low, ones before mid, unknowns through high, and twos after high. Each step shrinks the unknown region.

STEPS
  1. Set low = 0, mid = 0, high = n−1
  2. Loop while mid <= high — inclusive, because [mid, high] is the unclassified range
  3. a[mid] == 0 → swap(a[low], a[mid]), then low++ and mid++
  4. a[mid] == 1 → mid++ only; it is already in the middle region
  5. a[mid] == 2 → swap(a[mid], a[high]), then high-- and leave mid ALONE
  6. The loop ends when the unclassified region is empty
BRUTEO(n log n)
→
OPTIMALO(n)
↕ SCROLL
// Three regions and one unclassified gap [mid, high]. The invariant
// is a claim about RANGES, and every line below protects it.
void sortColors(vector<int>& a) {
    int low = 0, mid = 0, high = a.size() - 1;

    while (mid <= high) {                   // <= : [mid, high] is INCLUSIVE
        if (a[mid] == 0) swap(a[low++], a[mid++]);      // both advance
        else if (a[mid] == 1) mid++;                    // already home
        else swap(a[mid], a[high--]);                   // mid does NOT move
    }
}
TIMEO(n)every element is classified exactly once in a single pass
SPACEO(1)three indices; the swaps are in place
TRAP

After swapping a 2 with high, inspect the incoming value before advancing mid.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / DUTCH NATIONAL FLAG ARRAYS I · VISUAL LESSON
STEP 1 / 5

Only three values can appear.

Sort an array containing only 0, 1 and 2. Comparison sorting is more work than the alphabet requires.

 20
 01
 12
 23
 04
↓
 00
 01
 12
 23
 24

Counting each value and rewriting takes O(n) time in two passes. Three-way partition achieves O(n) time in one scan.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
40 / MECHANISM UNIT 06 · VOTE · CODE MIRRORED

Cancel different values

A true majority survives pair cancellation. Verify the candidate only when existence is not guaranteed.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
41 / DRILL UNIT 06 · Boyer-Moore Voting · 1 OF 2

Quick check

DRILL 01 · RECALL

Run only the voting pass on [1,2,3]. Which candidate is left at the end?

The candidate is 3. The 1 and 2 cancel, then 3 becomes the candidate. Since no value appears more than half the time, a second pass would reject 3.

DRILL 02 · TRACE

On [2,2,1,3,2], what are the candidate and count just after reading 3?

The candidate variable still holds 2 and the count is 0. The first two 2s raised the count to 2, then 1 and 3 brought it back to 0. The next value starts a new count.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
42 / DRILL UNIT 06 · Boyer-Moore Voting · 2 OF 2

Quick check

DRILL 01 · BUG

LeetCode 169 guarantees a majority. Which related problem still requires counting the final candidates?

int cand = 0, cnt = 0;
for (int v : a) {
    if (cnt == 0) cand = v;
    cnt += (v == cand) ? 1 : -1;
}
return cand;                    // no verify

Majority Element II asks for values that appear more than n/3 times. Either candidate can fall short, so count both before returning them.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
43 / PROBLEM #09 · VOTING · MED

Majority Element

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

A majority appears more than n/2 times.

INTUITION

Cancel pairs of different values. A true majority cannot be completely cancelled, so the survivor is the only possible answer.

STEPS
  1. Keep a candidate and a count, both initially meaningless
  2. For each value: if count is 0, adopt this value as the candidate
  3. Increment count when the value equals the candidate, decrement otherwise
  4. After the pass the candidate is the ONLY possible majority element
  5. Second pass: count the candidate's actual occurrences
  6. Return it only if that count exceeds n/2 — otherwise no majority exists
BRUTEO(n) time · O(n) space
→
OPTIMALO(n)
↕ SCROLL
// Unequal elements annihilate in pairs. A value holding more than half
// cannot be fully cancelled, so it is the ONLY POSSIBLE survivor -- which
// is not the same as proof that it IS the majority. Hence pass two.
int majorityElement(vector<int>& a) {
    int cand = 0, cnt = 0;

    for (int v : a) {
        if (cnt == 0) cand = v;             // prefix cancelled: restart here
        cnt += (v == cand) ? 1 : -1;        // agree, or annihilate
    }
    int c = 0;
    for (int v : a) c += (v == cand);       // VERIFY -- this IS the algorithm
    return c > a.size() / 2 ? cand : -1;
}
TIMEO(n)two sequential passes, both linear — still O(n)
SPACEO(1)a candidate and a counter, nothing else
TRAP

LC169 guarantees a majority. Without that guarantee, count the candidate in a second pass.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / BOYER-MOORE VOTING ARRAYS I · VISUAL LESSON
STEP 1 / 5

A majority means more than half.

Frequency counting works. Pair cancellation finds the only possible majority with constant extra space.

frequency > floor(n / 2)

A value appearing exactly half the time is not a majority. Keep the existence guarantee separate from the algorithm.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
44 / MECHANISM UNIT 07 · KADANE · CODE MIRRORED

Extend or start again?

cur is the best sum ending here. best is the largest cur seen anywhere. Keep them separate.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
45 / DRILL UNIT 07 · Kadane's Algorithm · 1 OF 2

Quick check

DRILL 01 · RECALL

Why does Kadane’s algorithm start best at a[0] instead of 0?

The subarray must contain at least one value. For [-3,-1,-2], the answer is −1. Starting best at 0 would return 0.

DRILL 02 · TRACE

On [-2,1,-3,4,-1,2,1,-5,4], what does cur become when Kadane reads the first 4?

It becomes 4. The previous cur is −2, so extending gives 2. Starting at 4 gives a larger sum.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
46 / DRILL UNIT 07 · Kadane's Algorithm · 2 OF 2

Quick check

DRILL 01 · BUG

On [-2,1,-3,4,-1,2,1,-5,4], this code returns 5 instead of 6. What does cur measure at the end?

int cur = a[0];
for (int i = 1; i < n; i++)
    cur = max(a[i], cur + a[i]);
return cur;                     // no best

cur is the best sum ending at the final index. The best subarray anywhere is [4,-1,2,1] with sum 6. Track the largest cur seen and return that.

DRILL 02 · TRANSFER

In Stock I, what do you track to find the best buy price for a sale today?

Track the cheapest price seen so far. Subtract it from today’s price and keep the largest profit. If every trade would lose money, return 0.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
47 / PROBLEM #10 · KADANE · MED

Maximum Subarray

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

Find the maximum sum of a non-empty contiguous subarray.

INTUITION

cur is the best sum ending here: extend the previous run or start at this element. best is the largest cur seen anywhere.

STEPS
  1. Set cur = best = a[0]; a subarray must be non-empty, so never start at 0
  2. For each later element, compute max(a[i], cur + a[i])
  3. That is the whole decision: start fresh here, or extend what you were carrying
  4. Assign the winner to cur — the best run ending at this index
  5. Update best = max(best, cur) on every element, not only at resets
  6. Return best — cur alone is the best run ending at the LAST index, which is different
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
// One decision per element: extend the run, or start over here.
// cur  = best run ENDING AT i.   best = best run ANYWHERE so far.
// Collapsing those two into one variable is how this usually breaks.
int maxSubArray(vector<int>& a) {
    int cur = a[0], best = a[0];            // NOT 0 - handles all-negative input

    for (int i = 1; i < a.size(); i++) {
        cur  = max(a[i], cur + a[i]);       // a prefix that hurts is dropped
        best = max(best, cur);              // record on EVERY element
    }
    return best;
}
TIMEO(n)one pass, one comparison and one max per element
SPACEO(1)two integers, regardless of input size
TRAP

Initialize from a[0], not zero. Return best, not the sum ending at the final element.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
48 / PROBLEM #11 · KADANE · MED

Best Time to Buy and Sell Stock

MED kadane ▶ SOLVE ON LEETCODEKadane on the difference array. The running value becomes today's price minus the cheapest price so far, and the reset becomes 'today is the new cheapest' -- same two lines, different quantity.
SIGNAL — WHAT GIVES IT AWAY

Buy before selling; making no trade is allowed.

INTUITION

Track the cheapest price seen so far. Compare today's possible profit with the best profit already found.

STEPS
  1. Set cheap = a[0] and best = 0; zero profit is always achievable by not trading
  2. For each later day, first update cheap = min(cheap, a[i])
  3. Then compute a[i] − cheap, the best profit achievable selling today
  4. Keep best = max(best, that value)
  5. Return best — the ordering constraint is honoured because cheap only ever looks backwards
BRUTEO(n²)
→
OPTIMALO(n)
-int maxSubArray(vector<int>& a) {-    int cur = a[0], best = a[0];            // NOT 0 - handles all-negative input+int maxProfit(vector<int>& a) {+    int cheap = a[0], best = 0;             // 0: not trading is always allowed       for (int i = 1; i < a.size(); i++) {-        cur  = max(a[i], cur + a[i]);       // a prefix that hurts is dropped-        best = max(best, cur);              // record on EVERY element+        cheap = min(cheap, a[i]);           // the best day to have bought+        best  = max(best, a[i] - cheap);    // record before moving on     }     return best; }
TIMEO(n)one pass, one min and one max per day
SPACEO(1)two integers
TRAP

Global maximum minus minimum ignores time order. Keep best at least zero.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / KADANE'S ALGORITHM ARRAYS I · VISUAL LESSON
STEP 1 / 7

A negative prefix cannot help.

For a non-empty maximum-sum subarray, decide whether to extend the previous ending sum or restart here.

cur = max(x, previous_cur + x)

Enumerating all start/end pairs with a running sum costs O(n²). A negative prefix only makes every future extension worse.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
49 / MECHANISM UNIT 08 · SIGNSPLIT · CODE MIRRORED

Give each sign its own slots

Write positives at 0,2,4,... and negatives at 1,3,5,... . This version assumes equal counts and preserves their order.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
50 / DRILL UNIT 08 · Rearrange by Sign · 1 OF 2

Quick check

DRILL 01 · RECALL

Why do the two write pointers always write to different slots?

The positive pointer uses indices 0, 2, 4, and so on. The negative pointer uses 1, 3, 5, and so on. These sets of indices never overlap.

DRILL 02 · TRACE

Rearrange [3,1,-2,-5,2,-4] by sign, starting with a positive. What is the result and where does 1 go?

The positives [3,1,2] fill indices 0, 2, 4. The negatives [-2,-5,-4] fill indices 1, 3, 5. The result is [3,-2,1,-5,2,-4], with 1 at index 2.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
51 / DRILL UNIT 08 · Rearrange by Sign · 2 OF 2

Quick check

DRILL 01 · TRANSFER

What can go wrong with the two write pointers when the counts of positive and negative values differ?

With three positives in an array of length 4, the positive pointer tries indices 0, 2, and 4. Index 4 is outside the array. For this variant, collect both groups, alternate while both have values, then add the rest in order.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
52 / PROBLEM #12 · WRITE-POINTER · MED

Rearrange Array Elements by Sign

MED write-pointer ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Equal counts of positive and negative values; alternate signs while preserving each sign's order.

INTUITION

Write positives into positions 0,2,4,... and negatives into 1,3,5,... of a new array. Reading left to right preserves their order.

STEPS
  1. Allocate a result array of the same length
  2. Set pos = 0 and neg = 1 — the first even and first odd slot
  3. Walk the input once in its original order
  4. A positive goes to out[pos], then pos += 2
  5. A negative goes to out[neg], then neg += 2
  6. Return the result; both cursors land exactly at the end because the counts are equal
BRUTEO(n) time · O(n) space, two lists
→
OPTIMALO(n)
↕ SCROLL
// Two destination cursors, each stepping by TWO. One visits only even
// indices and the other only odd ones, so they are disjoint by construction
// and no bounds check between them is ever needed.
vector<int> rearrangeArray(vector<int>& a) {
    vector<int> out(a.size());
    int pos = 0, neg = 1;                   // first even slot, first odd slot

    for (int v : a) {
        if (v > 0) { out[pos] = v; pos += 2; }
        else       { out[neg] = v; neg += 2; }
    }
    return out;                             // order kept within each sign
}
TIMEO(n)one pass, one write per element
SPACEO(n)the result array — the problem returns a new arrangement, so this is inherent
TRAP

The even/odd placement assumes equal counts and starts positive. This uses O(n) extra space.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / REARRANGE BY SIGN ARRAYS I · VISUAL LESSON
STEP 1 / 5

Preserve order within each sign.

The local problem has equal positive and negative counts, no zeros, and starts with a positive.

 40
 -21
 -52
 73
↓
 40
 -21
 72
 -53

Sorting by sign or swapping arbitrary pairs can destroy the required relative order.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
53 / MECHANISM UNIT 11 · SETZERO · CODE MIRRORED

Mark first, erase later

Use row 0 and column 0 as markers, with a separate col0 flag. Clear bottom-up so each marker survives until its last use.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
54 / DRILL UNIT 11 · The Matrix as Its Own Flag · 1 OF 2

Quick check

DRILL 01 · RECALL

Why do we save a separate flag for column 0 in Set Matrix Zeroes?

a[0][0] already marks whether row 0 needs to be cleared. A separate flag tracks column 0 so the two decisions stay independent.

DRILL 02 · TRACE

In this version of Set Matrix Zeroes, why does the second pass work from the bottom up?

Rows below row 0 still need its column markers. Processing row 0 last keeps those markers available. In each row, handle column 0 after reading its row marker.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
55 / DRILL UNIT 11 · The Matrix as Its Own Flag · 2 OF 2

Quick check

DRILL 01 · BUG

What goes wrong if we clear a row or column as soon as we find a zero?

for (r) for (c)
    if (a[r][c] == 0) {
        for (k) a[r][k] = a[k][c] = 0;  // zero it now
    }

The scan can treat a zero it just wrote as a zero from the original matrix. That can clear extra rows and columns. Record the markers first, then clear the cells.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
56 / PROBLEM #15 · INDEX-ALGEBRA · MED

Set Matrix Zeroes

MED index-algebra ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Zero every row and column that originally contains a zero.

INTUITION

Use the first row and column as markers. Save their own zero flags first; mark the interior, clear it, then apply the saved flags.

STEPS
  1. Scan the matrix; for each zero, set a[r][0] = 0 and either a[0][c] = 0 or col0 = true
  2. a[0][0] can only hold one mark, so column 0 uses the standalone col0 boolean
  3. Second pass runs from the bottom-right corner backwards toward the top-left
  4. Zero any interior cell whose row-marker a[r][0] or column-marker a[0][c] is zero
  5. Handle column 0 last, from col0, so its markers survive until read
  6. The markers live in cells read last, which is why traversal order matters
BRUTEO(m·n) time · O(m+n) space
→
OPTIMALO(m·n)
↕ SCROLL
// The matrix stores its own bookkeeping: row 0 and column 0 become the
// marker strips. a[0][0] is the ONE collision -- it cannot mark both, so
// column 0's fate lives in a single boolean.
void setZeroes(vector<vector<int>>& a) {
    int m = a.size(), n = a[0].size();
    bool col0 = false;

    for (int r = 0; r < m; r++) {
        if (a[r][0] == 0) col0 = true;
        for (int c = 1; c < n; c++)
            if (a[r][c] == 0) a[r][0] = a[0][c] = 0;    // leave notes, do not clear
    }
    for (int r = m - 1; r >= 0; r--) {                  // bottom-up: read before overwrite
        for (int c = n - 1; c >= 1; c--)
            if (a[r][0] == 0 || a[0][c] == 0) a[r][c] = 0;
        if (col0) a[r][0] = 0;                          // column 0 handled last
    }
}
TIMEO(m·n)two passes over the matrix
SPACEO(1)one boolean beyond the matrix itself — the first row and column ARE the storage
TRAP

Do not erase while discovering original zeros: newly written zeros would create false markers.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / THE MATRIX AS ITS OWN FLAG ARRAYS I · VISUAL LESSON
STEP 1 / 5

New zeros must not become evidence.

Zero every row and column containing an ORIGINAL zero.

123406789
→
103000709

Erasing immediately creates fresh zeros that could wrongly erase additional rows and columns.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
57 / MECHANISM UNIT 12 · ROTATE · CODE MIRRORED

Transpose, then reverse rows

Swapping across the diagonal reflects a square matrix. Reversing each row completes the clockwise turn.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
58 / DRILL UNIT 12 · Transpose & Reverse · 1 OF 2

Quick check

DRILL 01 · RECALL

When transposing in place, what would happen if the inner loop started at c = 0 instead of c = r + 1?

The loop would swap a[r][c] with a[c][r] and later swap them back. Starting at r + 1 visits each pair once and leaves the diagonal alone.

DRILL 02 · TRACE

Transpose [[1,2,3],[4,5,6],[7,8,9]], then reverse each row. What is row 0 after each step?

Transposing turns the first column into row 0, so it becomes [1,4,7]. Reversing that row gives [7,4,1].

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
59 / DRILL UNIT 12 · Transpose & Reverse · 2 OF 2

Quick check

DRILL 01 · TRANSFER

For a 90° counterclockwise rotation, in which order should you transpose and reverse the rows?

Reverse each row first, then transpose. A clockwise turn uses the same two steps in the opposite order.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
60 / PROBLEM #16 · INDEX-ALGEBRA · MED

Rotate Image

MED index-algebra ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Rotate a square matrix clockwise by 90 degrees in place.

INTUITION

Transpose across the main diagonal, then reverse each row. Together these map (r,c) to (c,n-1-r).

STEPS
  1. Transpose: for each r, swap a[r][c] with a[c][r] for all c > r
  2. Start the inner loop at c = r+1 so each pair is swapped once, not twice
  3. The main diagonal maps to itself and is left untouched
  4. Reverse each row to flip the transposed matrix left-to-right
  5. The result is the input rotated 90° clockwise, computed in place
  6. For anticlockwise, reverse the rows first and then transpose
BRUTEO(n²) time · O(n²) space, with a copy
→
OPTIMALO(n²)
↕ SCROLL
// 90 clockwise = transpose, then reverse each row. Both are reflections,
// and their composition is the rotation. The inner loop starts at r+1 so
// each pair swaps ONCE -- running the full square would undo the transpose.
void rotate(vector<vector<int>>& a) {
    int n = a.size();

    for (int r = 0; r < n; r++)
        for (int c = r + 1; c < n; c++)
            swap(a[r][c], a[c][r]);         // reflect across the main diagonal
    for (auto& row : a)
        reverse(row.begin(), row.end());    // flip left-to-right
}
TIMEO(n²)each element is touched a constant number of times
SPACEO(1)swaps in place; no auxiliary matrix
TRAP

Swap each off-diagonal pair once. Transpose alone reflects the matrix; it does not rotate it.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / TRANSPOSE & REVERSE ARRAYS I · VISUAL LESSON
STEP 1 / 5

Track one cell through the turn.

In an n × n matrix, a clockwise quarter-turn sends (r,c) to (c,n−1−r).

123456789
→
741852963

Copying each value to a fresh matrix follows this formula directly, but costs O(n²) extra space.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
61 / MECHANISM UNIT 13 · SPIRAL · CODE MIRRORED

Peel off one boundary at a time

Visit top, right, bottom, left. Shrink after each pass and recheck bounds before revisiting a row or column.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
62 / DRILL UNIT 13 · Four Shrinking Bounds · 1 OF 2

Quick check

DRILL 01 · RECALL

In Spiral Matrix, why check top <= bot again before reading the bottom row?

Reading the top row moves top down. If there was only one row left, top is now past bot. The check prevents reading the same row twice.

DRILL 02 · TRACE

What are the first six values in spiral order for [[1,2,3,4],[5,6,7,8],[9,10,11,12]]?

Read 1, 2, 3, 4 across the top. Then read 8 and 12 down the right side, starting below the top row.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
63 / DRILL UNIT 13 · Four Shrinking Bounds · 2 OF 2

Quick check

DRILL 01 · BUG

Remove the two checks inside the spiral loop. What does it return for the single row [[1,2,3]]?

while (top <= bot && left <= right) {
    // ... top row, right col ...
    for (c = right; c >= left; c--) out.push(a[bot][c]);
    bot--;
    // ... left col, no guard ...
}

It reads [1,2,3] across the top, then reads 2 and 1 again on the way back. The bottom-row check should skip that second pass because no rows remain.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
64 / PROBLEM #17 · INDEX-ALGEBRA · MED

Spiral Matrix

MED index-algebra ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Visit a rectangular matrix clockwise from its outer edge inward.

INTUITION

Traverse top, right, bottom and left, shrinking the corresponding boundary after each pass. Repeat while rows and columns remain.

STEPS
  1. Set top=0, bottom=m−1, left=0, right=n−1
  2. Walk the top row left→right, then top++
  3. Walk the right column top→bottom, then right--
  4. If top <= bottom, walk the bottom row right→left, then bottom--
  5. If left <= right, walk the left column bottom→top, then left++
  6. Repeat while top <= bottom and left <= right
BRUTEO(m·n) time · O(m·n) visited-set
→
OPTIMALO(m·n)
↕ SCROLL
// Four bounds that only shrink. The two inner guards are the whole
// problem: without them a lone final row or column is emitted twice.
vector<int> spiralOrder(vector<vector<int>>& a) {
    int top = 0, bot = a.size() - 1, left = 0, right = a[0].size() - 1;
    vector<int> out;

    while (top <= bot && left <= right) {
        for (int c = left; c <= right; c++) out.push_back(a[top][c]);
        top++;
        for (int r = top; r <= bot; r++) out.push_back(a[r][right]);
        right--;
        if (top <= bot) {                            // guard: still a row left?
            for (int c = right; c >= left; c--) out.push_back(a[bot][c]);
            bot--;
        }
        if (left <= right) {                         // guard: still a column left?
            for (int r = bot; r >= top; r--) out.push_back(a[r][left]);
            left++;
        }
    }
    return out;
}
TIMEO(m·n)each cell is emitted exactly once
SPACEO(1)four integer bounds; the output list is not counted as working space
TRAP

Recheck bounds before the bottom and left passes, or a final single row or column is visited twice.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / FOUR SHRINKING BOUNDS ARRAYS I · VISUAL LESSON
STEP 1 / 5

Peel the outer boundary.

Spiral order visits the top edge, right edge, bottom edge, then left edge.

123456789
1 → 2 → 3 → 6 → 9 → 8 → 7 → 4; then 5

The next layer is a smaller rectangle. Four bounds describe everything still unvisited.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
65 / MECHANISM UNIT 09 · NEXTPERM · CODE MIRRORED

Make the smallest larger arrangement

Find the rightmost ascent, swap its pivot with the rightmost larger value, then reverse the suffix.

ONE TRACK, EVERY ALGORITHM
CODE MIRROR
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
66 / DRILL UNIT 09 · Next Permutation · 1 OF 2

Quick check

DRILL 01 · RECALL

In Next Permutation, why is reversing the part after the pivot enough?

After the swap, the values after the pivot are still in non-increasing order. Reversing puts them in non-decreasing order, the smallest arrangement of those values.

DRILL 02 · TRACE

Find the next permutation of [1,3,5,4,2]. Which value is the pivot, what does it swap with, and what is the result?

The pivot is 3. Swap it with 4, the smallest value to its right that is greater than 3. Reverse the remaining part to get [1,4,2,3,5].

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
67 / DRILL UNIT 09 · Next Permutation · 2 OF 2

Quick check

DRILL 01 · BUG

What can go wrong if you pick the first value greater than the pivot by scanning from the left of the suffix?

int j = i + 1;
while (j < n && a[j] > a[i]) j++;  // first value above the pivot
swap(a[i], a[j - 1]);

You can pick a value that is too large. On [1,3,5,4,2], scanning from the left picks 5. Scanning from the right finds 4, which gives the smaller increase we need.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
68 / PROBLEM #13 · CONSTRUCT · MED

Next Permutation

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

Produce the next lexicographically larger arrangement in place.

INTUITION

Find the rightmost ascent. Swap its pivot with the rightmost larger value, then reverse the descending suffix into its smallest order.

STEPS
  1. Scan i from n−2 leftwards while a[i] >= a[i+1] — stop at the pivot
  2. If no pivot exists the array is fully descending: reverse it and return
  3. Scan j from n−1 leftwards for the first value greater than a[i]
  4. Swap a[i] and a[j] — the smallest possible increase at the pivot
  5. The suffix is still descending, so reverse it to make it ascending and minimal
  6. Reversing rather than sorting is O(n) and correct because of that guarantee
BRUTEO(n! · n)
→
OPTIMALO(n)
↕ SCROLL
// A descending suffix is ALREADY the largest arrangement of its values,
// so the change must happen at the last position with room to grow.
void nextPermutation(vector<int>& a) {
    int n = a.size(), i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;         // find the pivot

    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;                   // RIGHTMOST value above it
        swap(a[i], a[j]);                           // smallest possible increase
    }
    reverse(a.begin() + i + 1, a.end());            // descending -> ascending
}
TIMEO(n)at most three linear scans over the array
SPACEO(1)a handful of indices; every move is a swap
TRAP

If no ascent exists, reverse the entire array: the order wraps to the smallest arrangement.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
EXPLAIN / NEXT PERMUTATION ARRAYS I · VISUAL LESSON
STEP 1 / 5

Change as little as possible.

Find the next arrangement in dictionary order: compare left to right; the first different value decides which is larger.

 10
 41
 32
 23
next →
 20
 11
 32
 43

Generating and sorting all permutations grows factorially. Instead, preserve the longest possible prefix.

Try PREDICT in the animation: choose the next move before it runs.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
69 / RECALL MIXED PRACTICE

WHICH APPROACH FITS?

DRILL 01 · TRANSFER

How can you find the longest run of consecutive values in an unsorted array in expected O(n) time?

Put the values in a hash set. Start counting from x only if x-1 is absent. This walks each run once.

DRILL 02 · RECALL

You need the number of subarrays with sum k. What should the map store and how do you use it?

Store how often each prefix sum has appeared. At each step, add the count of earlier prefixes equal to prefix - k.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
70 / INDEPENDENT PRACTICE NO METHOD GIVEN

Choose the method yourself

Remove every occurrence of x from an unsorted array, in place. Keep the order of the remaining values and return their count. Try [3,1,3,2], x=3. Values after the returned count do not matter.

Write and run your code in your editor or the judge. Explain why it works.

Need a hint?

Read every value once. Where should the next kept value go?

Check your reasoning

Return 2; the first two values must be [1,2]. Start w=0. For each a[r] not equal to x, write a[w]=a[r], then increase w. Writing never reaches unread input. Test all removed → 0, none removed → n, empty → 0. O(n) time, O(1) space.

Self-reported; saved on this browser only. Not a judge result.

Next session: try again without the hint. Later this week: solve it among other topics. If you needed help, explain the missing idea before retrying.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
71 / INDEPENDENT PRACTICE NO METHOD GIVEN

Choose the method yourself

Return true if a non-empty subarray sums to k, otherwise false. Integers may be negative. Try [4,−1,2], k=3, and [2], k=0. Write an approach before opening help.

Write and run your code in your editor or the judge. Explain why it works.

Need a hint?

Think about what the sum at two boundaries tells you. Do you need a count or only existence?

Check your reasoning

Answers true and false. Track earlier prefix sums in a set starting with 0. After adding each value, check for sum−k before inserting the new sum. This avoids accepting an empty subarray. Expected O(n) time and O(n) space. Explain why always shrinking when the sum is too large is unsafe.

Self-reported; saved on this browser only. Not a judge result.

Next session: try again without the hint. Later this week: solve it among other topics. If you needed help, explain the missing idea before retrying.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
72 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

A quick reference. Use a pattern only when its assumptions fit.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Write pointer
O(n)
O(1)
Keep a valid prefix; never overwrite unread values
XOR / range sum
O(n)
O(1)
Use only when the pairing or range assumptions hold
Hash map / set
O(n) expected
O(n)
Remember partners; start consecutive runs at their boundary
Three-way partition
O(n)
O(1)
Track known regions and shrink the unknown region
Majority vote
O(n)
O(1)
Cancel pairs; verify if a majority is not guaranteed
Kadane / stock I
O(n)
O(1)
Best ending sum / cheapest earlier price: different state
Prefix frequencies
O(n) expected
O(n)
Count prefixes equal to current sum minus k; seed zero
Matrix traversal
O(rows × cols)
O(1) extra
Mark before mutation; keep row/column boundaries valid
Next permutation
O(n)
O(1)
Rightmost ascent; next larger successor; reverse suffix
INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
73 / CLOSE STEP 03 · DECK 1 OF 2

EIGHTEEN DOWN

Re-solve anything you needed help with. Then try an unseen array problem before deck 2.

00%
OF THIS DECK SOLVED
← ALL TOPICSDECK 2 · HARD →STEP 02 · SORTING

Original visual lessons, one per unit. Problem links are LeetCode.

INVARIANT · ARRAYS · ONE PASS · TWO INDICES · DECK 1 OF 2
■ TOO SMALL TO READ
1280×720
INVARIANT · STEP 03 · DECK 1 OF 2

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.