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.
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.
r reads; w marks the next free slot. Keep the unique values in the prefix before w.
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.
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.
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.
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.
Sorted input; keep one copy of each value in place.
The prefix before w holds the unique values kept so far. Scan with r; write only when a value differs from the last keeper.
// 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 }
// 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. public int removeDuplicates(int[] a) { if (a.length == 0) return 0; int w = 1; // a[0] is always a keeper for (int r = 1; r < a.length; r++) if (a[r] != a[w - 1]) // new vs the last value KEPT a[w++] = a[r]; return w; // w is a COUNT, so it IS the length }
# Two indices, one list. 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. def remove_duplicates(a): if not a: return 0 w = 1 # a[0] is a keeper by definition for r in range(1, len(a)): if a[r] != a[w - 1]: # differs from the LAST KEPT value? a[w] = a[r] # commit it, then widen the answer w += 1 return w # w counted keepers, so it IS the length
Return the kept length. Values beyond that prefix do not matter.
The input is sorted. Put one copy of each value at the front, in place.
Return 3. Only the first three slots count; the tail does not need clearing.
Insert into an ordered set, then copy its values back into the array.
We can avoid the extra container by using the order already present.
Once a larger value appears, the previous value cannot return later.
Keep the first value of each run. A single scan is enough.
Start w = 1 for a non-empty array. At r = 2, the value 5 differs from the last keeper, 2.
w is the next free slot and the number kept. Compare a[r] with a[w−1].
The first w slots contain one copy of each value seen so far. This first part is called a prefix.
A write cannot destroy future input. Each read advances once: O(n) time, O(1) extra space. Empty input returns 0.
After compacting [4, 4, 4], what must the function return?
Then run the animation, answer the drills, and implement it without the code mirror.
Try PREDICT in the animation: choose the next move before it runs.
For a right rotation: reverse everything, reverse the first k values, then reverse the rest. Reduce k modulo n first.
Swap each non-zero into the next prefix slot. Advance w only for a non-zero; the displaced zero moves behind the kept prefix.
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.
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].
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.
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.
Move zeros to the end while preserving non-zero order.
Write each non-zero value into the next free slot, then fill the remaining suffix with zeros. The write pointer never destroys unread input.
// 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 }
// The write pointer again, but SWAPPING because every element must // survive: the zero displaced from w travels to r, which is already read. public void moveZeroes(int[] a) { int w = 0; // oldest slot still owed a non-zero for (int r = 0; r < a.length; r++) if (a[r] != 0) { int t = a[w]; a[w] = a[r]; a[r] = t; // swap, never copy w++; } }
# The write pointer again, but SWAPPING because every element must # survive: the zero displaced from w travels to r, which is already read. def move_zeroes(a): w = 0 # oldest slot still owed a non-zero for r in range(len(a)): if a[r] != 0: a[w], a[r] = a[r], a[w] # order kept: written as they were read w += 1
Keep the non-zero values in their original order; arbitrary swaps can break stability.
Rotate right by k without an extra array.
Reduce k modulo n. Reverse the whole array, then the first k values and the rest to restore their order.
// 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 }
// Reversal rotation. The first reversal puts the right BLOCKS in the // right places; the other two fix the order inside each block. public void rotate(int[] a, int k) { int n = a.length; k %= n; // k may exceed n - this is in the tests reverse(a, 0, n - 1); // 1. the whole array reverse(a, 0, k - 1); // 2. the first k reverse(a, k, n - 1); // 3. everything after } private void reverse(int[] a, int l, int r) { while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; } }
# Reversal rotation. The first reversal puts the right BLOCKS in the # right places; the other two fix the order inside each block. def rotate(a, k): n = len(a) k %= n # k may exceed n - this is in the tests def rev(lo, hi): while lo < hi: a[lo], a[hi] = a[hi], a[lo] lo, hi = lo + 1, hi - 1 rev(0, n - 1) # 1. blocks swap sides, both backwards rev(0, k - 1) # 2. fix the block now at the front rev(k, n - 1) # 3. fix the block now at the back
Use k %= n. For a generalized empty-array input, return before taking modulo.
Move every non-zero value forward without changing its relative order.
A temporary list works in O(n) space. A write pointer builds the same non-zero prefix inside the input.
When a[r] is non-zero, swap it with a[w] and advance w. A zero advances only r.
The displaced zero moves to r. The non-zeros keep encounter order, and the suffix ends up zero-filled. O(n) time, O(1) extra space; copying then filling is another valid variant.
A right rotation by 2 moves the final two values to the front.
For n > 0, reduce k modulo n. Repeated one-step shifts can take O(nk); a temporary buffer takes extra space.
For our RIGHT-rotation problem, reverse all values, then the first k, then the rest.
| Operation | Array |
|---|---|
| Reverse all | 5 4 3 2 1 |
| Reverse first 2 | 4 5 3 2 1 |
| Reverse rest | 4 5 1 2 3 |
Reversing all gives reverse(B) · reverse(A). Reversing each block restores its internal order: B · A. Total O(n) time, O(1) extra space.
The lecture derives LEFT rotation. The local judge problem requires RIGHT rotation.
Do not copy the reversal order across variants. This judge guarantees n ≥ 1; a general-purpose version should return early on empty input before k %= n.
Right-rotate [1,2,3,4,5] by k = 7. What comes first?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
STEP 1 / 4
Two sorted arrays. The first has spare slots at the end.
Merge into the first array. The dots are spare slots, not values. A temporary result is a valid starting approach.
Writing 1 into the first slot would destroy the unread 2.
Compare the last unread values. The larger one belongs at the end, where there is free space.
Read 8 and 9: write 9. Next read 8 and 3: write 8.
| Step | First array |
|---|---|
| write 9 | 2 5 8 · · 9 |
| write 8 | 2 5 8 · 8 9 |
| write 5 | 2 5 8 5 8 9 |
| finish | 1 2 3 5 8 9 |
Start i=m−1, j=n−1, w=m+n−1. After each write, decrease w and the pointer you read. Remaining values from array 2 must be copied; remaining values in array 1 are already placed.
Close the walkthrough before coding.
Merge [2,5,8,0,0,0] and [1,3,9], with m=n=3. Then test an empty first input and an empty second input.
Write and run your code in your editor or the judge. Explain why it works.
Merge Sorted Array ↗Work backwards. Stop only when every value from the second array has been used.
Expected [1,2,3,5,8,9]. Every write fills its final position. While j≥0, w=i+j+1 is greater than i, so unread values in the first array are safe. O(m+n) time, O(1) extra space.
Self-reported; saved on this browser only. Not a judge result.
The spare-capacity rule matters. This is not the same problem as merging two full arrays without extra space.
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 ↗The next kept value must not become a third copy. What would you compare it with?
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.
x XOR x = 0. Fold the values and watch the unpaired value survive. The pairing assumption matters.
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.
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.
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.
Exactly one value is missing from 0 through n.
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.
// 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 }
// 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. public int missingNumber(int[] a) { int n = a.length, x = 0; for (int i = 0; i < n; i++) x ^= i ^ a[i]; // index against value return x ^ n; // and the index n itself }
# XOR the full range against what is actually present. Every value # that IS there gets folded twice and cancels; the hole is folded once. # Python ints never overflow, so the sum version is safe here -- but the # XOR version is the one that ports to C++ unchanged. def missing_number(a): n, x = len(a), 0 for i, v in enumerate(a): x ^= i ^ v # index and value, both folded return x ^ n # index n has no element to pair with
Promote to a wider type before multiplying n*(n+1); casting after multiplication is too late.
Find the longest uninterrupted run of ones.
Increment run on a one; reset it on a zero. Track best separately so an earlier run is not lost.
// 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; }
// 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. public int findMaxConsecutiveOnes(int[] a) { int run = 0, best = 0; for (int v : a) { run = (v == 1) ? run + 1 : 0; // extend, or reset to nothing best = Math.max(best, run); // record BEFORE moving on } return best; }
# 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. def find_max_consecutive_ones(a): run = best = 0 for v in a: run = run + 1 if v == 1 else 0 # a 0 ends the streak entirely best = max(best, run) # record here, not at the break return best
A zero resets run to 0. Count consecutive ones, not the total number of ones.
Every value occurs twice except one.
XOR is associative, x XOR x is zero, and x XOR zero is x. Folding the array cancels every pair.
// 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 }
// 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. public int singleNumber(int[] a) { int x = 0; // 0 is XOR's identity for (int v : a) x ^= v; return x; }
# 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. from functools import reduce from operator import xor def single_number(a): return reduce(xor, a, 0) # 0 is XOR's identity
The pairing assumption is essential. XOR does not solve arbitrary frequency counts.
For Single Number, every value appears twice except one. Order does not matter.
x ⊕ x = 0 and 0 ⊕ x = x. Associativity and commutativity let us group matching values without sorting.
A frequency map uses O(n) space. One XOR accumulator uses O(1) fixed-width space.
| Read | Accumulator |
|---|---|
| 6 | 6 |
| 3 | 5 |
| 6 | 3 |
Intermediate XOR can exceed the largest operand: 3 ⊕ 5 = 6. It stays within their bit width. The pairing guarantee is essential.
The local problem uses n distinct values from 0..n, with one absent.
All present values cancel; the absent value remains. The lecture uses 1..N instead—adjust the endpoints to the statement.
Expected sum minus observed sum also isolates the missing value.
Use a wide enough type before multiplying in C++/Java. Both sum and XOR take O(n) time; neither fixes duplicate or out-of-range input.
This problem is about adjacent positions, not pair cancellation.
| Input | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| run | 1 | 2 | 0 | 1 | 2 | 3 | 0 |
| best | 1 | 2 | 2 | 2 | 2 | 3 | 3 |
Increase run on 1; reset it on 0. Keep the maximum separately so a final zero cannot erase the best run. O(n) time, O(1) space.
One value appears once. What must be true of every other value in Single Number?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Before storing x, look for target - x among earlier values. The map remembers their indices.
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.
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].
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.
Return two different indices whose values sum to the target.
For each x, look for target-x among earlier values. If absent, store x and its index for later elements.
// 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 {}; }
// 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. public int[] twoSum(int[] a, int t) { Map<Integer, Integer> seen = new HashMap<>(); // value -> its index for (int i = 0; i < a.length; i++) { Integer j = seen.get(t - a[i]); // CHECK first if (j != null) return new int[]{j, i}; seen.put(a[i], i); // then store } return new int[]{-1, -1}; }
# 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 dict answers # that in O(1). Check BEFORE storing, or a[i] pairs with itself. def two_sum(a, t): seen = {} # value -> index it was seen at for i, v in enumerate(a): need = t - v # the ONE partner that works if need in seen: # has it already gone past? return [seen[need], i] seen[v] = i # store AFTER checking return []
Look up before inserting, or an element may incorrectly pair with itself.
For target 10 and current value 7, the needed earlier value is 3.
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.
Process [4,7,3] with target 10. The map stores value → original index.
| Index / value | Look for | Map before query | Action |
|---|---|---|---|
| 0 / 4 | 6 | {} | store 4 → 0 |
| 1 / 7 | 3 | {4:0} | store 7 → 1 |
| 2 / 3 | 7 | {4:0,7:1} | return [1,2] |
Only earlier indices are eligible. Inserting first could match an element with itself when target = 2 × value.
For [5,5], target 10, the second 5 finds the first 5 at a different index.
Duplicates are allowed. Reusing one index is not. Hash operations give O(n) expected time and O(n) space overall.
Sorted two pointers can answer whether a pair exists. Returning original indices requires retaining their mapping.
The lecture separates these two variants. Sorting costs O(n log n); it is not a linear-time replacement for the map.
For [5,2], target 10, may the first 5 produce [0,0]?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Start at x only when x-1 is absent. Each distinct value is then visited in one consecutive run.
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).
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.
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.
Consecutive values can appear anywhere; input order is irrelevant.
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.
// 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; }
// 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). public int longestConsecutive(int[] a) { Set<Integer> s = new HashSet<>(); for (int v : a) s.add(v); int best = 0; for (int v : s) { if (s.contains(v - 1)) continue; // THE guard: only run starts int len = 1; while (s.contains(v + len)) len++; best = Math.max(best, len); } return best; }
# 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). def longest_consecutive(a): s = set(a) # dedupes for free best = 0 for v in s: if v - 1 in s: continue # not a head - skip x, length = v, 1 while x + 1 in s: # walk the run once x, length = x + 1, length + 1 best = max(best, length) return best
Iterate distinct values and start only at run boundaries. Restarting from every value can become quadratic.
For [9,4,2,3,2,10], the longest consecutive sequence is 2,3,4.
Sorting and scanning works in O(n log n), skipping duplicates. A hash set supports expected O(n) time without sorting.
A value x starts a sequence precisely when x−1 is absent.
| Set value | Has predecessor? | Start a walk? |
|---|---|---|
| 2 | No | Yes: 2,3,4 |
| 3 | Yes: 2 | No |
| 4 | Yes: 3 | No |
| 9 | No | Yes: 9,10 |
| 10 | Yes: 9 | No |
Iterate distinct values in the set, not repeated input copies. Otherwise duplicate run starts can repeat the same long walk.
The inner walks visit disjoint runs. A value belongs to exactly one run.
There is one predecessor check per distinct value and one forward walk per run. With expected O(1) hash operations: O(n) time, O(n) space.
A set collapses repeated values; duplicates neither extend nor break a run.
| Input | Longest length |
|---|---|
| [] | 0 |
| [6,6,6] | 1 |
| [-2,0,-1,-1] | 3 |
Guard x−1 and x+1 overflow if a language permits full-range integer inputs; the judge’s bounds may already exclude those extremes.
The set is {2,3,4,9,10}. Which values start runs?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
STEP 1 / 3
A prefix is the first part of an array. P[i] is the sum of the first i values.
| i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| a[i] | 3 | -1 | 4 | 2 | — |
| P[i] | 0 | 3 | 2 | 6 | 8 |
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.
Find the sum from index 1 through index 2: −1 + 4.
P[3] includes indices 0,1,2. Subtracting P[1] removes index 0. For inclusive endpoints l and r, use P[r+1]−P[l].
Use a=[3,−1,4,2]. Predict the answer before opening the check.
Implement range sums. Check [0,3], [1,1] and [2,3]. Can you answer many queries without rescanning?
Write and run your code in your editor or the judge. Explain why it works.
Range Sum Query — Immutable ↗Build the totals once. Be clear whether the right endpoint is included.
Answers: 8, −1, 6. Build in O(n), answer each query in O(1), use O(n) space. Negative values work too.
Self-reported; saved on this browser only. Not a judge result.
Alternative: CSES Static Range Sum Queries. Choose one. CSES uses 1-based inclusive endpoints and needs 64-bit sums.
If this is already easy without help, move on. This bridge is not extra mandatory volume.
STEP 1 / 4
For [2,3,4,5], the answer at index 1 is 2 × 4 × 5 = 40.
A fresh loop for every index takes O(n²). Division is not allowed. A suffix is the last part of an array.
Walk left to right. Store the running product before multiplying by the current value.
| index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| input | 2 | 3 | 4 | 5 |
| product before | 1 | 2 | 6 | 24 |
Start with 1, the value that changes nothing when multiplied. Store these products directly in the answer array.
Walk right to left with a running product, starting at 1.
| index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| before | 1 | 2 | 6 | 24 |
| after | 60 | 20 | 5 | 1 |
| answer | 60 | 40 | 30 | 24 |
Multiply answer[i] by the running product, then include a[i] for the next step. Two passes: O(n) time and O(1) extra space excluding the required output.
Try [2,0,4]. What belongs at the zero’s position?
Implement without division. Test [2,3,4,5], [2,0,4], [0,3,0] and [-2,3,4].
Write and run your code in your editor or the judge. Explain why it works.
Product of Array Except Self ↗For each position, combine only values strictly before it and strictly after it.
Expected [60,40,30,24], [0,8,0], [0,0,0], [12,−8,−6]. A value is excluded because neither running product includes it at the time of the update.
Self-reported; saved on this browser only. Not a judge result.
Explain why storing or multiplying before updating the running product matters.
A subarray sums to k when its boundary prefixes differ by k. Seed {0:1}; query before recording the current prefix.
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.
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.
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.
Count contiguous subarrays summing to k; negative values are allowed.
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.
// 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; }
// 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. public int subarraySum(int[] a, int k) { Map<Integer, Integer> count = new HashMap<>(); count.put(0, 1); // the empty prefix int prefix = 0, total = 0; for (int v : a) { prefix += v; total += count.getOrDefault(prefix - k, 0); // how many starts qualify count.merge(prefix, 1, Integer::sum); } return total; }
# 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. from collections import defaultdict def subarray_sum(a, k): cnt = defaultdict(int); cnt[0] = 1 # the empty prefix counts running = total = 0 for v in a: running += v total += cnt[running - k] # every earlier P(j)=running-k closes one cnt[running] += 1 # record AFTER checking return total
Query before recording the current prefix. Ordinary shrinking windows fail with negatives; zeros also require careful counting.
For [3,−1,4,2], the totals before each boundary are [0,3,2,6,8].
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.
Let P[i] be the sum of the first i values. The sum over [l,r) is P[r]−P[l].
Enumerating all subarrays with a running sum costs O(n²). Remember earlier prefix sums to count matches at each right boundary.
Trace [2,−2,2], k = 2. Begin with freq[0] = 1 for the empty prefix.
| Read | Prefix | Need prefix−k | Earlier matches | Total |
|---|---|---|---|---|
| 2 | 2 | 0 | 1 | 1 |
| -2 | 0 | -2 | 0 | 1 |
| 2 | 2 | 0 | 2 | 3 |
The same prefix can appear multiple times; each occurrence is a different starting boundary. A set would undercount.
Update the running prefix, add freq[prefix−k] to the answer, then increment freq[prefix].
For k = 0, inserting first would pair a boundary with itself and count an empty subarray. For [0,0], the correct count is 3.
For target 3, [4,−1] is valid. Discarding 4 merely because the current sum exceeds 3 would miss it.
Prefix differences do not require monotonic sums. Expected O(n) time and O(n) map space; use wide counters when n(n+1)/2 can overflow.
The algebra is shared, but the map value depends on the question.
Do not substitute the last index or a frequency into the longest-length version. Keeping the earliest occurrence gives the longest span.
How many non-empty subarrays of [0,0] have sum 0?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
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.
Which earlier boundary gives the greatest distance to the current boundary?
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.
Zeros sit before low; ones before mid; twos after high. After moving a 2, inspect the incoming value.
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.
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.
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.
The array contains only 0, 1 and 2; partition it in place.
Keep zeros before low, ones before mid, unknowns through high, and twos after high. Each step shrinks the unknown region.
// 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 } }
// Three regions and one unclassified gap [mid, high]. The invariant // is a claim about RANGES, and every line below protects it. public void sortColors(int[] a) { int low = 0, mid = 0, high = a.length - 1; while (mid <= high) { // <= : [mid, high] is INCLUSIVE if (a[mid] == 0) { int t = a[low]; a[low++] = a[mid]; a[mid++] = t; // both advance } else if (a[mid] == 1) { mid++; // already where it belongs } else { int t = a[mid]; a[mid] = a[high]; a[high--] = t; // mid STAYS } } }
# Three regions and one unclassified gap [mid, high]. The invariant # is a claim about RANGES, and every line below protects it. def sort_colors(a): low, mid, high = 0, 0, len(a) - 1 while mid <= high: # <= : [mid, high] is INCLUSIVE if a[mid] == 0: a[low], a[mid] = a[mid], a[low] # both advance low, mid = low + 1, mid + 1 elif a[mid] == 1: mid += 1 # already home else: a[mid], a[high] = a[high], a[mid] # mid does NOT move high -= 1
After swapping a 2 with high, inspect the incoming value before advancing mid.
Sort an array containing only 0, 1 and 2. Comparison sorting is more work than the alphabet requires.
Counting each value and rewriting takes O(n) time in two passes. Three-way partition achieves O(n) time in one scan.
mid points at the next unknown value. Only the unknown region needs work.
Initially low = mid = 0 and high = n−1. Stop when mid > high: no unknown values remain.
The update depends on a[mid], not on the element we hope is there.
| a[mid] | Action | Advance |
|---|---|---|
| 0 | swap with a[low] | low++, mid++ |
| 1 | already in the middle | mid++ |
| 2 | swap with a[high] | high-- only |
A swap from high brings an unclassified value to mid. Inspect it before advancing. Each step shrinks the unknown region.
Begin with [1,2,0], low = 0. After scanning 1, mid = 1 and high = 2.
Advancing mid now would stop too early and leave [1,0,2]. Keeping mid lets us move the incoming 0 to the front. O(n) time, O(1) space.
After handling a 2 at mid, which pointer must stay at the incoming value?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
A true majority survives pair cancellation. Verify the candidate only when existence is not guaranteed.
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.
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.
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.
A majority appears more than n/2 times.
Cancel pairs of different values. A true majority cannot be completely cancelled, so the survivor is the only possible answer.
// 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; }
// 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. public int majorityElement(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) if (v == cand) c++; // VERIFY -- this IS the algorithm return c > a.length / 2 ? cand : -1; }
# 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. def majority_element(a): cand, cnt = None, 0 for v in a: if cnt == 0: cand = v # prefix cancelled: restart here cnt += 1 if v == cand else -1 # agree, or annihilate return cand if a.count(cand) > len(a) // 2 else -1 # VERIFY
LC169 guarantees a majority. Without that guarantee, count the candidate in a second pass.
Frequency counting works. Pair cancellation finds the only possible majority with constant extra space.
A value appearing exactly half the time is not a majority. Keep the existence guarantee separate from the algorithm.
In [7,7,2,7,3], remove one 7 with 2 and another 7 with 3.
Removing unlike pairs cannot eliminate a strict majority: each removed pair contains at most one copy of it.
Choose a candidate when balance is zero. Equal values add a vote; different values cancel one.
| Read | Candidate | Balance |
|---|---|---|
| 7 | 7 | 1 |
| 7 | 7 | 2 |
| 2 | 7 | 1 |
| 7 | 7 | 2 |
| 3 | 7 | 1 |
Balance 1 does not mean that 7 occurs once. It measures uncancelled votes. O(n) time, O(1) space.
On [1,2,3], cancellation still leaves a candidate, but no value occurs more than half the time.
The local judge guarantees existence, so verification is optional. Our displayed code retains the second pass and returns −1 if no majority exists.
Without an existence guarantee, is the surviving candidate always the answer?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
cur is the best sum ending here. best is the largest cur seen anywhere. Keep them separate.
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.
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.
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.
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.
Find the maximum sum of a non-empty contiguous subarray.
cur is the best sum ending here: extend the previous run or start at this element. best is the largest cur seen anywhere.
// 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; }
// 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. public int maxSubArray(int[] a) { int cur = a[0], best = a[0]; // NOT 0 - handles all-negative for (int i = 1; i < a.length; i++) { cur = Math.max(a[i], cur + a[i]); // restart, or extend best = Math.max(best, cur); } return best; }
# 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. def max_sub_array(a): cur = best = a[0] # NOT 0 - handles all-negative input for v in a[1:]: cur = max(v, cur + v) # a prefix that hurts is dropped best = max(best, cur) # record on EVERY element return best
Initialize from a[0], not zero. Return best, not the sum ending at the final element.
Buy before selling; making no trade is allowed.
Track the cheapest price seen so far. Compare today's possible profit with the best profit already found.
-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; }
-public int maxSubArray(int[] a) {- int cur = a[0], best = a[0]; // NOT 0 - handles all-negative+public int maxProfit(int[] a) {+ int cheap = a[0], best = 0; // 0: not trading is always allowed for (int i = 1; i < a.length; i++) {- cur = Math.max(a[i], cur + a[i]); // restart, or extend- best = Math.max(best, cur);+ cheap = Math.min(cheap, a[i]); // the best day to have bought+ best = Math.max(best, a[i] - cheap); // record before moving on }- return best;+ return best; // Kadane on the difference array }
-def max_sub_array(a):- cur = best = a[0] # NOT 0 - handles all-negative input+def max_profit(a):+ cheap, best = a[0], 0 # 0: not trading is always allowed for v in a[1:]:- cur = max(v, cur + v) # a prefix that hurts is dropped- best = max(best, cur) # record on EVERY element+ cheap = min(cheap, v) # the best day to have bought+ best = max(best, v - cheap) # record before moving on return best
Global maximum minus minimum ignores time order. Keep best at least zero.
For a non-empty maximum-sum subarray, decide whether to extend the previous ending sum or restart here.
Enumerating all start/end pairs with a running sum costs O(n²). A negative prefix only makes every future extension worse.
Trace [-4,3,-1,5,-6]. The best answer can end before the array does.
| Read | -4 | 3 | -1 | 5 | -6 |
|---|---|---|---|---|---|
| cur | -4 | 3 | 2 | 7 | 1 |
| best | -4 | 3 | 3 | 7 | 7 |
Return best, not cur. Initializing from the first value preserves the non-empty answer on all-negative arrays.
A negative element can belong inside the optimum: [3,-1,5] has sum 7.
Our recurrence is equivalent to discarding a negative accumulated prefix. The lecture uses sum/reset; it updates the answer before resetting.
To return the subarray too, track the start of the current candidate and save its bounds when best improves.
For ties, any maximum-sum subarray is sufficient unless the statement specifies a tie rule. O(n) time, O(1) auxiliary state.
Checking every buy/sell pair repeats the same search for a minimum.
| Sale price | 6 | 2 | 7 |
|---|---|---|---|
| Cheapest earlier price | 3 | 3 | 2 |
| Profit | 3 | -1 | 5 |
For prices [8,3,6,2,7], the best earlier buy can be remembered as you scan. Keep the best profit at 0 if every trade loses money. This turns O(n²) pairs into O(n) work.
Choose one buy before one sell. At each sell day, the cheapest earlier price is the best possible buy.
| Price | 8 | 3 | 6 | 2 | 7 |
|---|---|---|---|---|---|
| cheapest so far | 8 | 3 | 3 | 2 | 2 |
| best profit | 0 | 0 | 3 | 3 | 5 |
The lecture checks profit before updating the minimum. Our code updates the minimum first: a new minimum contributes only 0, equivalent to no trade. Falling prices return 0.
Maximum NON-EMPTY subarray sum for [-8,-3,-5]?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Write positives at 0,2,4,... and negatives at 1,3,5,... . This version assumes equal counts and preserves their order.
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.
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.
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.
Equal counts of positive and negative values; alternate signs while preserving each sign's order.
Write positives into positions 0,2,4,... and negatives into 1,3,5,... of a new array. Reading left to right preserves their order.
// 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 }
// 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. public int[] rearrangeArray(int[] a) { int[] out = new int[a.length]; int pos = 0, neg = 1; // even slots / odd slots for (int v : a) { if (v > 0) { out[pos] = v; pos += 2; } else { out[neg] = v; neg += 2; } } return out; }
# 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. def rearrange_array(a): out = [0] * len(a) pos, neg = 0, 1 # first even slot, first odd slot for v in a: if v > 0: out[pos] = v; pos += 2 else: out[neg] = v; neg += 2 return out # order kept within each sign
The even/odd placement assumes equal counts and starts positive. This uses O(n) extra space.
The local problem has equal positive and negative counts, no zeros, and starts with a positive.
Sorting by sign or swapping arbitrary pairs can destroy the required relative order.
A baseline splits into two lists and interleaves. We can write directly to the output instead.
Scan left to right; each value goes to the next slot of its sign. Each sign keeps its encounter order.
Two cursors do not make this an in-place algorithm.
| Input read | Output slots |
|---|---|
| 4 | [4, ·, ·, ·] |
| −2 | [4, −2, ·, ·] |
| −5 | [4, −2, ·, −5] |
| 7 | [4, −2, 7, −5] |
O(n) time and O(n) output space. Equal counts guarantee that neither cursor runs out of matching slots.
The lecture’s follow-up allows one sign to be more common.
The simple alternating-slot method no longer suffices. If zeros are allowed, define where they belong before choosing an algorithm.
What property does left-to-right insertion preserve?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Use row 0 and column 0 as markers, with a separate col0 flag. Clear bottom-up so each marker survives until its last use.
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.
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.
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.
Zero every row and column that originally contains a zero.
Use the first row and column as markers. Save their own zero flags first; mark the interior, clear it, then apply the saved flags.
// 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 } }
// 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. public void setZeroes(int[][] a) { int m = a.length, n = a[0].length; boolean col0 = false; for (int r = 0; r < m; r++) { if (a[r][0] == 0) col0 = true; // column 0 marked separately for (int c = 1; c < n; c++) if (a[r][c] == 0) { a[r][0] = 0; a[0][c] = 0; } } for (int r = m - 1; r >= 0; r--) { // BACKWARDS: markers read last 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; } }
# 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. def set_zeroes(a): m, n = len(a), len(a[0]) col0 = False for r in range(m): if a[r][0] == 0: col0 = True for c in range(1, n): if a[r][c] == 0: a[r][0] = a[0][c] = 0 # leave notes, do not clear for r in range(m - 1, -1, -1): # bottom-up: read before overwrite for c in range(n - 1, 0, -1): if a[r][0] == 0 or a[0][c] == 0: a[r][c] = 0 if col0: a[r][0] = 0 # column 0 handled last
Do not erase while discovering original zeros: newly written zeros would create false markers.
Zero every row and column containing an ORIGINAL zero.
Erasing immediately creates fresh zeros that could wrongly erase additional rows and columns.
A row flag array and column flag array safely remember where original zeros occur.
This baseline takes O(rows × cols) time and O(rows + cols) space. An arbitrary sentinel such as −1 is unsafe if it can occur in the input.
For each interior zero at (r,c), mark a[r][0] and a[0][c].
a[0][0] marks row 0. A separate col0 flag remembers whether column 0 originally contained a zero: one cell cannot independently encode both facts.
Our code walks bottom-up and right-to-left. Row 0 is processed last so its column markers stay intact.
Read a[r][0] before clearing that row’s first cell. Use col0 for column 0. O(rows × cols) time, O(1) extra space; the judge supplies a non-empty matrix.
A cell has a marked row but an unmarked column. Should it become zero?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Swapping across the diagonal reflects a square matrix. Reversing each row completes the clockwise turn.
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.
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].
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.
Rotate a square matrix clockwise by 90 degrees in place.
Transpose across the main diagonal, then reverse each row. Together these map (r,c) to (c,n-1-r).
// 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 }
// 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. public void rotate(int[][] a) { int n = a.length; for (int r = 0; r < n; r++) for (int c = r + 1; c < n; c++) { // r+1, not 0 int t = a[r][c]; a[r][c] = a[c][r]; a[c][r] = t; } for (int[] row : a) for (int l = 0, rr = n - 1; l < rr; l++, rr--) { int t = row[l]; row[l] = row[rr]; row[rr] = t; } }
# 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. def rotate(a): n = len(a) for r in range(n): for c in range(r + 1, n): a[r][c], a[c][r] = a[c][r], a[r][c] # reflect across the diagonal for row in a: row.reverse() # flip left-to-right
Swap each off-diagonal pair once. Transpose alone reflects the matrix; it does not rotate it.
In an n × n matrix, a clockwise quarter-turn sends (r,c) to (c,n−1−r).
Copying each value to a fresh matrix follows this formula directly, but costs O(n²) extra space.
Transpose by swapping a[r][c] with a[c][r].
Swap only one side of the diagonal, for example c > r. Swapping both sides would undo every exchange.
The transpose maps (r,c) → (c,r); reversing a row maps (c,r) → (c,n−1−r).
The composed mapping is exactly the clockwise turn. O(n²) time, O(1) extra space when swaps occur in place.
The in-place transpose-and-reverse method here assumes a square matrix.
A rectangular rotation changes shape; do not reuse square indexing blindly. A 1 × 1 matrix stays unchanged.
When transposing in place, which off-diagonal entries should you swap?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Visit top, right, bottom, left. Shrink after each pass and recheck bounds before revisiting a row or column.
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.
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.
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.
Visit a rectangular matrix clockwise from its outer edge inward.
Traverse top, right, bottom and left, shrinking the corresponding boundary after each pass. Repeat while rows and columns remain.
// 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; }
// Four bounds that only shrink. The two inner guards are the whole // problem: without them a lone final row or column is emitted twice. public List<Integer> spiralOrder(int[][] a) { int top = 0, bot = a.length - 1, left = 0, right = a[0].length - 1; List<Integer> out = new ArrayList<>(); while (top <= bot && left <= right) { for (int c = left; c <= right; c++) out.add(a[top][c]); top++; for (int r = top; r <= bot; r++) out.add(a[r][right]); right--; if (top <= bot) { // GUARD for (int c = right; c >= left; c--) out.add(a[bot][c]); bot--; } if (left <= right) { // GUARD for (int r = bot; r >= top; r--) out.add(a[r][left]); left++; } } return out; }
# Four bounds that only shrink. The two inner guards are the whole # problem: without them a lone final row or column is emitted twice. def spiral_order(a): top, bot, left, right = 0, len(a) - 1, 0, len(a[0]) - 1 out = [] while top <= bot and left <= right: for c in range(left, right + 1): out.append(a[top][c]) top += 1 for r in range(top, bot + 1): out.append(a[r][right]) right -= 1 if top <= bot: # guard: still a row left? for c in range(right, left - 1, -1): out.append(a[bot][c]) bot -= 1 if left <= right: # guard: still a column left? for r in range(bot, top - 1, -1): out.append(a[r][left]) left += 1 return out
Recheck bounds before the bottom and left passes, or a final single row or column is visited twice.
Spiral order visits the top edge, right edge, bottom edge, then left edge.
The next layer is a smaller rectangle. Four bounds describe everything still unvisited.
top and bottom bound rows; left and right bound columns.
| Traverse | Fixed coordinate | Then |
|---|---|---|
| left → right | top | top++ |
| top → bottom | right | right-- |
| right → left | bottom | bottom-- |
| bottom → top | left | left++ |
Continue while top ≤ bottom AND left ≤ right. The bounds are inclusive.
A single row is already exhausted after the top-edge pass.
Before the bottom edge, require top ≤ bottom. Before the left edge, require left ≤ right. Otherwise a final thin layer can be visited twice.
Each edge consumes previously unvisited cells. Each matrix cell is output exactly once.
Handle an empty matrix before accessing its first row. Test 1×1, one row, one column and a rectangular matrix.
Spiral order of a one-column matrix [[4],[5],[6]]?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
Find the rightmost ascent, swap its pivot with the rightmost larger value, then reverse the suffix.
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.
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].
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.
Produce the next lexicographically larger arrangement in place.
Find the rightmost ascent. Swap its pivot with the rightmost larger value, then reverse the descending suffix into its smallest order.
// 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 }
// A descending suffix is ALREADY the largest arrangement of its values, // so the change must happen at the last position with room to grow. public void nextPermutation(int[] a) { int n = a.length, 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--; // smallest value ABOVE it int t = a[i]; a[i] = a[j]; a[j] = t; } for (int l = i + 1, r = n - 1; l < r; l++, r--) { // reverse, not sort: int t = a[l]; a[l] = a[r]; a[r] = t; // the suffix descends } }
# A descending suffix is ALREADY the largest arrangement of its values, # so the change must happen at the last position with room to grow. def next_permutation(a): n = len(a) i = n - 2 while i >= 0 and a[i] >= a[i + 1]: i -= 1 # find the pivot if i >= 0: j = n - 1 while a[j] <= a[i]: j -= 1 # RIGHTMOST value above it a[i], a[j] = a[j], a[i] # smallest possible increase a[i + 1:] = reversed(a[i + 1:]) # descending -> ascending
If no ascent exists, reverse the entire array: the order wraps to the smallest arrangement.
Find the next arrangement in dictionary order: compare left to right; the first different value decides which is larger.
Generating and sorting all permutations grows factorially. Instead, preserve the longest possible prefix.
A suffix is the last part. If its values never increase from left to right, it is already its largest arrangement. Reordering only that suffix cannot make it larger.
Scan right-to-left for the first i with a[i] < a[i+1]. If no such i exists, the whole array is maximal: reverse it to wrap around.
In the descending suffix, its rightmost value greater than the pivot is the smallest eligible replacement.
| Step | Array |
|---|---|
| Original | 1 | 4 3 2 |
| Swap pivot 1 with 2 | 2 | 4 3 1 |
| Reverse suffix | 2 | 1 3 4 |
After increasing the pivot minimally, minimize the suffix. It is still non-increasing after the swap, so reversing is enough.
Equal values do not create a larger permutation.
Find a strict ascent and a strictly greater successor. A constant number of linear scans gives O(n) time and O(1) extra space.
Next permutation of [3,2,1], using wraparound?
Make a prediction, then test it in the animation. Code the problem independently afterward.
Try PREDICT in the animation: choose the next move before it runs.
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.
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.
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.
Read every value once. Where should the next kept value go?
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.
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.
Think about what the sum at two boundaries tells you. Do you need a count or only existence?
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.
A quick reference. Use a pattern only when its assumptions fit.
Re-solve anything you needed help with. Then try an unseen array problem before deck 2.
Original visual lessons, one per unit. Problem links are LeetCode.
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.