ONE TRACK, EVERY ALGORITHM
THE RESULT BEING BUILT
DOES IT MERGE?
YOUR CALL
Nothing in this deck is a new idea. Every one of these eight is two things from deck 1 stacked — 3Sum is sorting plus two pointers, Reverse Pairs is merge sort plus a counter, Max Product is Kadane with a second running value. Hard here means composed, and that is a much smaller thing to learn.
This is not a list of problems. It is 8 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
8 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Every card below names a pair of deck-1 patterns. That is the whole thesis of this deck: hard here means composed, and composition is a much smaller thing to learn than eight new tricks.
order inside the tuple is irrelevant, and duplicates must not repeat
SORT, FIX k−2 INDICES, CLOSE THE REST WITH TWO POINTERSO(nk−1) time · O(1) spacea condition on PAIRS across the whole array, and n is 10⁵
COUNT INSIDE MERGE SORT — BOTH HALVES ARE ALREADY SORTEDO(n log n) time · O(n) spacethe threshold caps how many answers can exist — here, at most two
TWO CANDIDATES, CANCEL IN PAIRS, THEN ALWAYS VERIFYO(n) time · O(1) spacetwo unknowns, and the values are a permutation of 1..n
TWO EQUATIONS: THE SUM AND THE SUM OF SQUARES (OR XOR BY BIT)O(n) time · O(1) spaceoverlap is a relation between pairs, but only adjacency matters once sorted
SORT BY START, THEN ONE SWEEP CARRYING THE OPEN INTERVALO(n log n) time · O(1) extranegatives flip the ordering, so the smallest value is a candidate for largest
KADANE CARRYING BOTH A RUNNING MAX AND A RUNNING MINO(n) time · O(1) spaceThe Hard rows are where the bound actually bites — 3Sum's brute force is legal at n = 300 and fatal at n = 3000. Type a value for n and the row that survives lights up.
THE GOLD-EDGED ROWS ARE WHERE THIS DECK LIVES · 3SUM IS O(n²) BY DESIGN, NOT BY FAILURE TO OPTIMISE
All 8 units. Unit 06 owns no sheet row — it is Count Inversions, kept because Reverse Pairs is unteachable without it. Deck 1's nine patterns are assumed throughout.
Every problem in this deck is a composition of two patterns from deck 1. Which pair does 3Sum stack?
Sorting + two pointers. And the order matters: the sort is not a tidying step, it is what creates the property the pointers need. On an unsorted array, a sum that is too small tells you nothing about which pointer to move — either could help. Once sorted, only one of them can, every single time. Read every hard problem in this deck as “which two things is this?” and they stop being memorisation.
4Sum sums four values that each fit in an int. Why is long long not optional?
It wraps to a negative number. LeetCode 18 allows values up to 10⁹, so four of them reach 4×10⁹ — past INT_MAX at ~2.1×10⁹. Signed overflow wraps to something negative, which then compares as less than the target, so the pointer moves the wrong way and you either miss quadruplets or record ones that do not sum correctly. No crash. A plausible, wrong, shorter answer. Accumulate in long long and the whole class of failure disappears.
This is 3Sum's duplicate handling after a hit. It returns triplets that are all individually correct, and the judge still rejects it. Which line?
else { out.push_back({a[i], a[lo], a[hi]}); lo++; hi--; // advance past the hit }
Moving one slot is not enough. With [-2, 0, 0, 2, 2], after recording [-2, 0, 2] the pointers land on the second 0 and the second 2 — which sum identically, so the same triplet is recorded again. You need while (lo < hi && a[lo] == a[lo-1]) lo++; and its mirror for hi. Three duplicate skips exist in 3Sum — one for the fixed index and one for each pointer — and the fixed-index one is the only one most people remember.
Pascal's Triangle looks like three different problems wearing one name, and the sheet quietly asks all three: print the whole triangle, print one row, or find a single entry. The unlock for every version is the same and it is worth more than the triangle itself — the binomial coefficient rolls. nCk = nC(k−1) × (n−k+1) / k, so each entry is built from its left neighbour with one multiply and one exact divide. No factorial is ever formed.
HOW DO YOU FIND ROW n OF PASCAL'S TRIANGLE WITHOUT COMPUTING A SINGLE FACTORIAL?
Why compute a row with the rolling formula nCk = nC(k−1)·(n−k+1)/k instead of the direct n! / (k!·(n−k)!)?
It sidesteps overflow entirely. n! explodes past 64 bits by n = 21, even when the final nCk is tiny and perfectly representable. The rolling form only ever holds values on the order of the answer itself, and — the part people distrust — each division is exact: nC(k−1)·(n−k+1) is always divisible by k, because it is a product of k consecutive integers over k. So plain integer arithmetic loses nothing. Computing a small result via a huge intermediate is a recurring anti-pattern, and this is the clean way out of it.
Building row 4 by rolling, you have nC2 = 6. What is nC3, and by what step?
nC3 = 6 × 2 / 3 = 4. The falling factor is (n−k+1) = (4−3+1) = 2 and the rising factor is k = 3. Note the order the visualiser uses — multiply first, then divide — so the intermediate 12 is divisible by 3 with no remainder. Row 4 comes out [1, 4, 6, 4, 1], and you can see the symmetry: nC3 = nC1 = 4. Step the MECHANISM slide in PREDICT mode and it asks you for each next entry.
The variant asks only for a single entry, C(n, k), for one row deep in the triangle. What is the cheapest correct approach?
Roll k times and stop. A single entry needs neither the triangle above it nor the rest of its row — you start at C(n,0) = 1 and apply the roll exactly k times, which is O(k) time and O(1) space. Building the whole triangle to reach one cell is O(n²), and the factorial formula reintroduces the overflow you just avoided. This is the third of Pascal's three questions, and recognising that all three share one mechanism is the entire point of treating it as a unit.
You never form a factorial. Each entry is the previous one times the falling factor (n−k+1) over the rising factor k — and that division is always exact, so no fractions and no overflow on the way to a value that would. One row is O(cols), the whole triangle O(rows²), and it reads the same backwards because nCk = nC(n−k).
“Pascal's Triangle” is really three requests behind one name — the whole triangle, a single row, or one entry — and the constraints tell you which. What they never want is a factorial: the moment you see C(n, k) with n past ~20, the signal is roll the coefficient, because n! overflows long before C(n, k) does.
Each row is the binomial coefficients nC0, nC1, … nCn, and adjacent coefficients are related by a clean roll: nCk = nC(k−1) × (n−k+1) / k. So start every row at 1 and multiply-then-divide across it. The division is exact because you are dividing a product of k consecutive integers by k, so integer arithmetic never drops a remainder, and no intermediate ever approaches the size of a factorial.
// The binomial coefficient ROLLS: nCk = nC(k-1) * (n-k+1) / k. // No factorial is ever formed, so nothing overflows on the way to a value // that would, and the division is always exact. vector<vector<int>> generate(int numRows) { vector<vector<int>> tri; for (int n = 0; n < numRows; n++) { vector<int> row = {1}; // nC0 is always 1 long long v = 1; for (int k = 1; k <= n; k++) { v = v * (n - k + 1) / k; // multiply then divide, exact row.push_back((int)v); } tri.push_back(row); } return tri; }
// The binomial coefficient ROLLS: nCk = nC(k-1) * (n-k+1) / k. // No factorial is ever formed, so nothing overflows on the way to a value // that would, and the division is always exact. public List<List<Integer>> generate(int numRows) { List<List<Integer>> tri = new ArrayList<>(); for (int n = 0; n < numRows; n++) { List<Integer> row = new ArrayList<>(); row.add(1); // nC0 is always 1 long v = 1; for (int k = 1; k <= n; k++) { v = v * (n - k + 1) / k; // multiply then divide, exact row.add((int) v); } tri.add(row); } return tri; }
# The binomial coefficient ROLLS: nCk = nC(k-1) * (n-k+1) // k. # No factorial is ever formed, so nothing overflows on the way to a value # that would, and the division is always exact. def generate(num_rows): tri = [] for n in range(num_rows): row, v = [1], 1 # nC0 is always 1 for k in range(1, n + 1): v = v * (n - k + 1) // k # multiply then divide, exact row.append(v) tri.append(row) return tri
Reaching for n! / (k!·(n−k)!). It is the textbook formula and it overflows a 64-bit integer at n = 21, returning a garbage coefficient for a value that would have fit in a byte. The rolling form never holds anything larger than the answer. The quieter trap is dividing before multiplying — v / k * (n−k+1) truncates, because v alone need not be divisible by k; only the product is. Multiply first, always.
The walkthrough for #01 Pascal's Triangle. Watch it, then go straight back and write it yourself.
Boyer–Moore, generalised. The majority-element trick found one value occurring more than n/2 times; here the threshold is more than n/3, which caps the number of answers at two — you cannot have three distinct values each exceeding a third of the array. So carry two candidates and two counts. The cancellation still works, but a non-matching vote now cancels from both counts at once, and the order of the checks becomes load-bearing.
HOW DO YOU FIND EVERY VALUE OCCURRING MORE THAN n/3 TIMES, IN O(1) SPACE?
Why can there be at most two values occurring more than ⌊n/3⌋ times?
Three would overflow the array. If three distinct values each appeared strictly more than n/3 times, their combined count would be strictly more than n — but there are only n elements. So at most two can qualify, and that counting fact is why two candidate slots suffice. The same reasoning generalises: “more than n/k” admits at most k−1 answers and needs k−1 slots. The data structure size is dictated by the threshold, not guessed.
This checks the empty slots before the equality tests. On [1, 1, 2] it mishandles the second 1. What happens?
for (int v : a) { if (n1 == 0) { c1 = v; n1 = 1; } else if (n2 == 0) { c2 = v; n2 = 1; } else if (v == c1) n1++; else if (v == c2) n2++; else { n1--; n2--; } }
The value 1 ends up in both slots. First 1 seeds c1. The second 1 should just increment n1 — but because the empty-slot check runs first and n2 is still 0, it seeds c2 = 1 too. Now a single value holds both candidacies and the algorithm can never track a genuine second majority. The fix is strict: test equality against existing candidates before ever filling an empty slot. It is the single ordering constraint in the whole method, and it is invisible until an early value repeats before a second distinct value appears.
After the vote you hold candidates 3 and 2. On the input the counts came out positive for both. Are you done?
Not done — verify both. The vote guarantees that any value exceeding n/3 is among your two survivors, but it never promises the survivors qualify. On [1, 2, 3] the vote proposes two candidates and the correct answer is the empty list. So re-scan, count each candidate's real occurrences, and keep only those strictly above ⌊n/3⌋. This is the same lesson as the n/2 case, sharpened: with n/3 there is no problem variant that guarantees an answer exists, so the verify pass is not optional even in principle.
“More than n/3” caps the answer at two values, so two candidates and two counts suffice. The subtle line is the order of the checks: the equality tests must come before the empty-slot tests, or a value equal to one candidate wrongly seeds the other. A non-matching vote cancels from both counts at once — and, as always with voting, the survivors are candidates until the verify pass confirms them.
“More than ⌊n/3⌋ times” is the whole signal, and it is doing two jobs at once: the fractional threshold says voting (cancel unequal elements), and the specific third caps the number of answers at two. Pair that with the near-universal follow-up — O(1) space, so no frequency map — and it is Boyer–Moore with two candidate slots.
Extend the majority-element vote to two candidates and two counts. Walk once: if the value matches a candidate, bump that count; otherwise, if a slot is empty, adopt the value there; otherwise it agrees with neither, so cancel one vote from both counts. After the pass the two survivors are the only possible answers — at most two values can exceed a third of the array — so a second pass counts their true frequencies and keeps only those that really clear the bar.
// n/3 admits at most TWO answers, so two candidate slots. The equality // tests must come BEFORE the empty-slot tests, or a repeated value seeds // the second slot with itself. A non-match cancels from BOTH counts. vector<int> majorityElement(vector<int>& a) { int c1 = 0, c2 = 1, n1 = 0, n2 = 0; // distinct start values for (int v : a) { if (v == c1) n1++; // equality FIRST else if (v == c2) n2++; else if (n1 == 0) { c1 = v; n1 = 1; } else if (n2 == 0) { c2 = v; n2 = 1; } else { n1--; n2--; } // cancel from both } int f1 = 0, f2 = 0; // VERIFY -- 229 guarantees nothing for (int v : a) { f1 += (v == c1); f2 += (v == c2); } vector<int> out; if (f1 > a.size() / 3) out.push_back(c1); if (f2 > a.size() / 3) out.push_back(c2); return out; }
// n/3 admits at most TWO answers, so two candidate slots. The equality // tests must come BEFORE the empty-slot tests, or a repeated value seeds // the second slot with itself. A non-match cancels from BOTH counts. public List<Integer> majorityElement(int[] a) { int c1 = 0, c2 = 1, n1 = 0, n2 = 0; // distinct start values for (int v : a) { if (v == c1) n1++; // equality FIRST else if (v == c2) n2++; else if (n1 == 0) { c1 = v; n1 = 1; } else if (n2 == 0) { c2 = v; n2 = 1; } else { n1--; n2--; } // cancel from both } n1 = 0; n2 = 0; for (int v : a) { if (v == c1) n1++; else if (v == c2) n2++; } List<Integer> out = new ArrayList<>(); if (n1 > a.length / 3) out.add(c1); // VERIFY: the vote only proposes if (n2 > a.length / 3) out.add(c2); return out; }
# n/3 admits at most TWO answers, so two candidate slots. The equality # tests must come BEFORE the empty-slot tests, or a repeated value seeds # the second slot with itself. A non-match cancels from BOTH counts. def majority_element(a): c1, c2, n1, n2 = 0, 1, 0, 0 # distinct start values for v in a: if v == c1: n1 += 1 # equality FIRST elif v == c2: n2 += 1 elif n1 == 0: c1, n1 = v, 1 elif n2 == 0: c2, n2 = v, 1 else: n1, n2 = n1 - 1, n2 - 1 # cancel from both return [c for c in (c1, c2) # VERIFY -- 229 guarantees nothing if a.count(c) > len(a) // 3]
Seeding the empty slots before testing equality. Put the n == 0 checks first and a value equal to candidate 1, arriving while slot 2 is still empty, seeds candidate 2 with that same value — one number holding both candidacies, and a real second majority can never be tracked. The other trap is the familiar one: skipping the verify pass. Unlike its n/2 cousin, this problem never guarantees an answer exists, so [1,2,3] must return the empty list, and only counting can tell you that.
The walkthrough for #02 Majority Element II. Watch it, then go straight back and write it yourself.
Two of deck 1's patterns, stacked. Sorting is not the answer here — it is the setup. An unsorted array tells you nothing when a sum comes out wrong: either pointer might fix it. A sorted array makes the choice forced, every single time, and that forcing is what collapses the O(n³) triple loop to O(n²). Everything hard about these two problems is then bookkeeping: which indices are fixed, and where the three duplicate skips go.
HOW DO YOU FIND EVERY TRIPLET SUMMING TO ZERO WITHOUT CHECKING EVERY TRIPLET?
The lecture insists the sort is what makes two pointers possible, not merely convenient. What breaks on an unsorted array?
The move stops being forced. On a sorted array, sum < target proves that moving hi left can only make things worse, so lo++ is the only justified action — and that is what lets you discard a whole region without examining it. Unsorted, either pointer might lead to the answer, so you cannot discard anything and you are back to checking all pairs. Two pointers is not a technique you apply to an array; it is a technique you apply to a monotonic one. Skipping duplicates gets easier too, but that is a bonus, not the reason.
On the sorted array [-4, -1, -1, 0, 1, 2] with i fixed at index 0 (value −4), lo=1 and hi=5. The sum is −4 + −1 + 2 = −3. What happens next, and why is the other move wrong?
lo++. The sum −3 is below the target 0, so you need more. Because the array is sorted, a[hi] is the largest value available in the window — moving hi left can only make the sum smaller, taking you further from zero. The only way up is a larger a[lo]. Note the answer is not “2 is too big”: 2 is the best value you have, and the reason to keep it is the same monotonicity. Step the MECHANISM slide in PREDICT mode — it asks you exactly this at every comparison.
Duplicate handling. Every triplet this emits is individually correct, and the judge still rejects the submission. Which line is at fault?
if (s == 0) { out.push_back({a[i], a[lo], a[hi]}); lo++; hi--; // move past the hit }
Advancing one slot is not the same as advancing past the duplicates. On [-2, 0, 0, 2, 2], after recording [-2, 0, 2] the pointers land on the second 0 and the second 2 — an identical sum, so the identical triplet is emitted again. You need while (lo < hi && a[lo] == a[lo-1]) lo++; and its mirror for hi. The problem says “unique” and that word is doing real work — it is the difference between a correct algorithm and an accepted submission.
4Sum is “3Sum with one more loop”. Measured as a code diff it changes 10 lines, past this deck's 6-line ceiling for calling something a variant. What actually changes beyond the extra loop?
Four things travel with that loop. The target stops being a hardcoded 0 and becomes a parameter; lo anchors to j+1 rather than i+1; the new fixed index needs its own duplicate skip guarded by j > i+1 and not j > 0; and the sum needs long long because four values near 10⁹ overflow. This is why the deck refuses to render it as a diff: it is true as a sentence and false as a diff, and a 10-line diff would make two genuinely different implementations look interchangeable.
Sorting is not the answer here, it is the setup. Once the array is monotonic a single comparison decides everything: too small and only lo moving right can raise the sum; too large and only hi moving left can lower it. There is never a choice to agonise over, which is precisely what an unsorted array does not give you. Watch the duplicate skips too — they happen in three places, and missing any one of them produces a list that looks right until the judge diffs it.
Three words do all the work: “triplets” (so k−2 = 1 index gets fixed and the rest is a two-pointer close), “unique” (so duplicate skipping is part of the algorithm, not a tidy-up), and the absence of any mention of indices in the output — you return values, so you are free to sort. That last one is the permission slip for the entire approach.
Sort first. Now fix the smallest member of the triplet at index i and ask a much easier question of the tail: find two values summing to −a[i]. Because the tail is sorted, a running sum that is too small can only be fixed by moving lo right, and one that is too big only by moving hi left — so each comparison discards a whole region rather than a single pair. That is what turns O(n³) into O(n²).
// Sort is the SETUP, not the answer: it makes a wrong sum tell you // which pointer to move. Unsorted, neither move would be justified. vector<vector<int>> threeSum(vector<int>& a) { sort(a.begin(), a.end()); // monotonic buys the pointers int n = a.size(); vector<vector<int>> out; for (int i = 0; i < n - 2; i++) { if (i && a[i] == a[i - 1]) continue; // skip 1 of 3: fixed index int lo = i + 1, hi = n - 1; while (lo < hi) { long long s = (long long)a[i] + a[lo] + a[hi]; if (s < 0) lo++; // too small: only lo can help else if (s > 0) hi--; // too big: only hi can help else { out.push_back({a[i], a[lo], a[hi]}); lo++; hi--; while (lo < hi && a[lo] == a[lo - 1]) lo++; // skip 2 of 3 while (lo < hi && a[hi] == a[hi + 1]) hi--; // skip 3 of 3 } } } return out; }
// Sort is the SETUP, not the answer: it makes a wrong sum tell you // which pointer to move. Unsorted, neither move would be justified. public List<List<Integer>> threeSum(int[] a) { Arrays.sort(a); // monotonic buys the pointers int n = a.length; List<List<Integer>> out = new ArrayList<>(); for (int i = 0; i < n - 2; i++) { if (i > 0 && a[i] == a[i - 1]) continue; // skip 1 of 3: fixed index int lo = i + 1, hi = n - 1; while (lo < hi) { long s = (long) a[i] + a[lo] + a[hi]; if (s == 0) { out.add(Arrays.asList(a[i], a[lo], a[hi])); while (lo < hi && a[lo] == a[lo + 1]) lo++; // skip BOTH sides while (lo < hi && a[hi] == a[hi - 1]) hi--; lo++; hi--; } else if (s < 0) lo++; // too small: raise the low else hi--; // too big: lower the high } } return out; }
# Sort is the SETUP, not the answer: it makes a wrong sum tell you # which pointer to move. Unsorted, neither move would be justified. def three_sum(a): a.sort() # monotonic buys the pointers n, out = len(a), [] for i in range(n - 2): if i and a[i] == a[i - 1]: continue # skip 1 of 3: fixed index lo, hi = i + 1, n - 1 while lo < hi: s = a[i] + a[lo] + a[hi] # Python ints never overflow if s < 0: lo += 1 # too small: only lo can help elif s > 0: hi -= 1 # too big: only hi can help else: out.append([a[i], a[lo], a[hi]]) lo, hi = lo + 1, hi - 1 while lo < hi and a[lo] == a[lo - 1]: lo += 1 # skip 2 of 3 while lo < hi and a[hi] == a[hi + 1]: hi -= 1 # skip 3 of 3 return out
There are three duplicate skips and most people write one. The fixed index is the memorable one; the two after a hit are the ones that get forgotten, and they are why a submission whose every triplet is individually correct still fails — the judge compares lists, and yours has [-2,0,2] twice. The second trap is quieter: sorting is only legal because the output is values. The moment a problem asks for indices, sorting destroys the answer and this whole approach is off the table.
The walkthrough for #03 3Sum. Watch it, then go straight back and write it yourself.
Identical to 3Sum in every respect except one: the target is given rather than zero, and one more index gets fixed. Read “quadruplets” as “k = 4, so fix k−2 = 2 indices and close the last two with pointers”. The generalisation is the point — kSum is one algorithm with a loop depth of k−2.
Everything from 3Sum, one level deeper. Fix i, then fix j inside it, then close lo and hi against a target reduced by both fixed values. The only genuinely new hazard is arithmetic rather than algorithmic: four values near 10⁹ overflow a 32-bit accumulator and wrap negative, which makes the comparison lie and sends the pointer the wrong way.
// kSum generalised: fix k-2 indices, close the last two with pointers. // The accumulator is long long because four ints near 1e9 WRAP NEGATIVE, // and a wrapped sum compares as "too small" and moves the wrong pointer. vector<vector<int>> fourSum(vector<int>& a, int t) { sort(a.begin(), a.end()); int n = a.size(); vector<vector<int>> out; for (int i = 0; i < n - 3; i++) { if (i && a[i] == a[i - 1]) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && a[j] == a[j - 1]) continue; // j > i+1, NOT j > 0 int lo = j + 1, hi = n - 1; while (lo < hi) { long long s = (long long)a[i] + a[j] + a[lo] + a[hi]; if (s < t) lo++; else if (s > t) hi--; else { out.push_back({a[i], a[j], a[lo], a[hi]}); lo++; hi--; while (lo < hi && a[lo] == a[lo - 1]) lo++; while (lo < hi && a[hi] == a[hi + 1]) hi--; } } } } return out; }
// kSum generalised: fix k-2 indices, close the last two with pointers. // The accumulator is long because four ints near 1e9 WRAP NEGATIVE in int, // and a wrapped sum compares as "too small" and moves the wrong pointer. public List<List<Integer>> fourSum(int[] a, int t) { Arrays.sort(a); int n = a.length; List<List<Integer>> out = new ArrayList<>(); for (int i = 0; i < n - 3; i++) { if (i > 0 && a[i] == a[i - 1]) continue; for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && a[j] == a[j - 1]) continue; // j > i+1, NOT j > 0 int lo = j + 1, hi = n - 1; while (lo < hi) { long s = (long) a[i] + a[j] + a[lo] + a[hi]; if (s == t) { out.add(Arrays.asList(a[i], a[j], a[lo], a[hi])); while (lo < hi && a[lo] == a[lo + 1]) lo++; while (lo < hi && a[hi] == a[hi - 1]) hi--; lo++; hi--; } else if (s < t) lo++; else hi--; } } } return out; }
# kSum generalised: fix k-2 indices, close the last two with pointers. # Python ints are arbitrary precision, so the overflow that bites the C++ # version cannot happen here -- which is itself worth noticing. def four_sum(a, t): a.sort() n, out = len(a), [] for i in range(n - 3): if i and a[i] == a[i - 1]: continue for j in range(i + 1, n - 2): if j > i + 1 and a[j] == a[j - 1]: continue # j > i+1, NOT j > 0 lo, hi = j + 1, n - 1 while lo < hi: s = a[i] + a[j] + a[lo] + a[hi] if s < t: lo += 1 elif s > t: hi -= 1 else: out.append([a[i], a[j], a[lo], a[hi]]) lo, hi = lo + 1, hi - 1 while lo < hi and a[lo] == a[lo - 1]: lo += 1 while lo < hi and a[hi] == a[hi + 1]: hi -= 1 return out
j > i + 1, never j > 0. The inner duplicate skip must compare against the previous j within this i, and guarding with j > 0 throws away the very first valid j whenever it happens to equal a[i] — so quadruplets containing a repeated value silently vanish. The second trap is the int accumulator: four values near 10⁹ wrap negative, the sum then reads as below target, lo advances when it should not, and you get a short answer list on the large tests only.
The walkthrough for #04 4Sum. Watch it, then go straight back and write it yourself.
Two of deck 1's ideas stacked: sort, then sweep. On its own, deciding whether any two of n intervals overlap is O(n²). But sort them by start and a hard fact appears — a new interval can only overlap the one you most recently kept, because every earlier kept interval starts no later and has already been closed off. So one pass carrying a single “current” interval merges everything, and the only line that bites is max() when you extend.
HOW DO YOU MERGE OVERLAPPING INTERVALS WITHOUT COMPARING EVERY PAIR?
After sorting by start, why is it enough to compare each interval against only the most recently kept one, rather than all kept intervals?
Sorted starts collapse the comparison. When you reach a new interval, every kept interval before the last began no later than the last one did — and if any of them still reached this far right, it would have merged with the last one already. So the last kept interval's end is the furthest-right boundary in play, and it is the only one a new interval can touch. That is the whole reason the sort turns O(n²) into O(n): it makes “which intervals could overlap” answerable by looking at exactly one.
When two intervals overlap, this sets the kept end to the new interval's end. On [[1,5],[2,3]] it returns [1,3]. What is wrong?
if (cur[0] <= last[1]) last[1] = cur[1]; // extend the kept interval else out.push_back(cur);
It needs max. When the incoming interval sits entirely inside the kept one — [2,3] inside [1,5] — its end (3) is smaller than the kept end (5), so assigning it directly shrinks the merged interval to [1,3] and silently drops coverage. last[1] = max(last[1], cur[1]) keeps whichever end reaches further. It is invisible whenever intervals happen to arrive in increasing-end order, which most hand-written examples do — the nested case is the one that catches it.
A related problem asks for the total length covered by the union of the intervals. How does this template change?
The skeleton is identical. Sort by start, sweep once carrying the current open interval, and every time a block closes (a non-overlap forces a new interval, or you reach the end) add its end − start to a total. You never need to store the merged list at all. A great many interval problems — union length, count of merged groups, the largest gap — are this one sweep with a different accumulator, which is exactly why the sweep is worth owning as a pattern rather than memorising Merge Intervals as a one-off.
Sorting is the setup, not the answer: once intervals are ordered by start, an overlap can only ever be with the interval you just kept, which collapses O(n²) pair-checking into a single pass. The one rule that bites is max() when extending — a short interval sitting entirely inside a long one must not shrink it.
“Merge all overlapping intervals” with intervals given unsorted. Overlap sounds like a pairwise relation — O(n²) — but the fix is the tell: whenever a problem is about intervals and order does not otherwise matter, sorting by start converts “which of these overlap” into “does this one touch the last one I kept”, and the whole thing becomes a single sweep.
Sort by start. Sweep left to right carrying one “current” interval. For each next interval, compare its start against the current interval's end: if it is less than or equal, they overlap, so extend the current end to the maximum of the two ends; otherwise there is a real gap, so close the current interval and start a new one. Sorted starts guarantee no earlier interval can reach past the current end, so comparing against just the last kept interval is sufficient.
// Sort by start, then ONE sweep: an overlap can only ever be with the // interval you just kept, because sorted starts mean nothing earlier reaches // further right. max() when extending -- a nested short interval must not shrink it. vector<vector<int>> merge(vector<vector<int>>& iv) { sort(iv.begin(), iv.end()); vector<vector<int>> out; for (auto& cur : iv) { if (out.empty() || cur[0] > out.back()[1]) out.push_back(cur); // real gap: keep separate else out.back()[1] = max(out.back()[1], cur[1]); // overlap: extend } return out; }
// Sort by start, then ONE sweep: an overlap can only ever be with the // interval you just kept, because sorted starts mean nothing earlier reaches // further right. max() when extending -- a nested short one must not shrink it. public int[][] merge(int[][] iv) { Arrays.sort(iv, (x, y) -> Integer.compare(x[0], y[0])); List<int[]> out = new ArrayList<>(); for (int[] cur : iv) { if (out.isEmpty() || cur[0] > out.get(out.size() - 1)[1]) out.add(cur); // real gap: keep separate else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]); } return out.toArray(new int[0][]); }
# Sort by start, then ONE sweep: an overlap can only ever be with the # interval you just kept, because sorted starts mean nothing earlier reaches # further right. max() when extending -- a nested short interval must not shrink it. def merge(iv): iv.sort() out = [] for cur in iv: if not out or cur[0] > out[-1][1]: out.append(cur[:]) # real gap: keep separate else: out[-1][1] = max(out[-1][1], cur[1]) # overlap: extend return out
Assigning kept.end = cur.end instead of max(...). When the incoming interval nests entirely inside the kept one, its end is smaller, so the direct assignment shrinks the merged interval and drops coverage — [[1,5],[2,3]] becomes [1,3]. It hides whenever ends happen to arrive in increasing order. The second trap is forgetting to sort, or sorting by end: the entire “only the last kept interval can overlap” guarantee rests on sorted starts, and without it the single-pass logic is simply wrong.
The walkthrough for #05 Merge Intervals. Watch it, then go straight back and write it yourself.
One number in 1..n appears twice and one is missing. Two unknowns, so one equation cannot pin them down — you need two independent equations. The cleanest pair is the sum and the sum of squares. Each has a closed form for a perfect 1..n, so the differences between actual and expected give you dup − missing and dup² − missing², and a line of algebra separates the two. O(1) space, one pass, no array of seen-flags.
HOW DO YOU FIND BOTH THE DUPLICATE AND THE MISSING NUMBER IN ONE PASS, O(1) SPACE?
The sum difference alone gives dup − missing. Why is that not enough, and what does the sum of squares add?
One equation, two unknowns is underdetermined. Knowing dup − missing = 3 is consistent with (4,1), (5,2), (100,97) and endlessly more. The sum of squares supplies a second relation, dup² − missing² = (dup−missing)(dup+missing), and dividing it by the first difference hands you dup + missing directly. Now you have both the difference and the sum of the two unknowns, which a pair of linear equations resolves uniquely. Counting unknowns and matching them with equations is the whole method, and it generalises to any “k values wrong” variant.
On [3, 2, 3, 4, 6, 5] (n = 6), the expected sum is 21 and expected sum of squares is 91. The actual sum is 23. What is dup − missing, and what is the duplicate?
dup − missing = 23 − 21 = 2, and the duplicate is 3. The actual sum of squares is 99, so the squares difference is 99 − 91 = 8, and 8 / 2 = 4 = dup + missing. Solving dup − missing = 2 with dup + missing = 4 gives dup = 3, missing = 1 — and indeed the array has two 3s and no 1. The MECHANISM slide accumulates both running totals and then walks the two-line solve.
An alternative avoids the sum of squares entirely using XOR. What does XOR-ing all the values with all of 1..n give you, and what is still needed?
XOR gives dup ⊕ missing, then a partition finishes it. Fold every array value and every index 1..n into one accumulator; the correctly-present values cancel in pairs and you are left with dup ⊕ missing. Any bit set in that result is a bit where dup and missing differ, so partition all the numbers into those with that bit and those without — dup and missing fall into different buckets, and XOR-ing each bucket isolates them. It is O(1) space with no overflow risk at all, which is its advantage over sum-of-squares. Two genuinely different derivations of the same answer — worth knowing both, because an interviewer may block one.
One duplicate and one missing value are two unknowns, so one equation cannot pin them down. Walk once and accumulate both the sum and the sum of squares, each measured against the closed-form total for a clean 1..n. Their differences give dup − missing and dup² − missing², and dividing the second by the first yields dup + missing — two linear equations, solved in O(1) space.
“Numbers 1..n, one is duplicated and one is missing, find both” — a complete known range with exactly two defects. That framing is the signal for an identity-based solution: because you know precisely what a clean array should sum and square to, the gaps between expected and actual pin down the two unknowns. The O(1)-space follow-up rules out the seen-array.
Two unknowns need two equations. Compute the running sum and running sum of squares of the array, and subtract the closed-form totals for a perfect 1..n. The first difference is dup − missing; the second is dup² − missing², which factors as (dup − missing)(dup + missing). Divide the second difference by the first to get dup + missing, and now two linear equations give both values immediately.
// Two unknowns, two equations. Sum gives dup-missing; sum of squares // gives dup^2-missing^2 = (dup-missing)(dup+missing). Dividing the second by // the first yields dup+missing, and two linear equations finish it. vector<int> findErrorNums(vector<int>& a) { long long n = a.size(), s = 0, s2 = 0; for (int v : a) { s += v; s2 += (long long)v * v; } long long d1 = s - n * (n + 1) / 2; // dup - missing long long d2 = s2 - n * (n + 1) * (2 * n + 1) / 6; // dup^2 - missing^2 long long sum = d2 / d1; // dup + missing int dup = (int)((d1 + sum) / 2); return {dup, (int)(sum - dup)}; }
// Two unknowns, two equations. Sum gives dup-missing; sum of squares // gives dup^2-missing^2 = (dup-missing)(dup+missing). Dividing the second by // the first yields dup+missing, and two linear equations finish it. public int[] findErrorNums(int[] a) { long n = a.length, s = 0, s2 = 0; for (int v : a) { s += v; s2 += (long) v * v; } long d1 = s - n * (n + 1) / 2; // dup - missing long d2 = s2 - n * (n + 1) * (2 * n + 1) / 6; // dup^2 - missing^2 long sum = d2 / d1; // dup + missing long dup = (d1 + sum) / 2; return new int[]{(int) dup, (int) (sum - dup)}; }
# Two unknowns, two equations. Sum gives dup-missing; sum of squares # gives dup^2-missing^2 = (dup-missing)(dup+missing). Dividing the second by # the first yields dup+missing, and two linear equations finish it. # (Python ints are unbounded, so the C++ overflow trap cannot bite here.) def find_error_nums(a): n = len(a) s = sum(a); s2 = sum(v * v for v in a) d1 = s - n * (n + 1) // 2 # dup - missing d2 = s2 - n * (n + 1) * (2 * n + 1) // 6 # dup^2 - missing^2 total = d2 // d1 # dup + missing dup = (d1 + total) // 2 return [dup, total - dup]
Accumulating in a 32-bit int. The sum of squares of 1..n is roughly n³/3, which passes INT_MAX by n ≈ 1800 — far below the constraint — so the running total wraps and every downstream value is garbage, with no crash. Use long long. The alternative XOR method sidesteps overflow entirely: XOR all values with all indices to get dup ⊕ missing, then split the numbers by a differing bit to separate them — worth knowing as a backup when an interviewer bars the arithmetic approach.
The walkthrough for #06 Set Mismatch. Watch it, then go straight back and write it yourself.
This unit owns no sheet problem — it is the mechanism the next one is built on. Count Inversions asks how many pairs are out of order, and the answer piggybacks on merge sort: once the two halves are sorted, when you take a value from the right half before the left is exhausted, every remaining left value is larger, so each is an inversion with it — counted in bulk as len(L) − i rather than one at a time. That bulk count is the whole idea, and Reverse Pairs is a two-line variation on it.
HOW DO YOU COUNT OUT-OF-ORDER PAIRS FASTER THAN CHECKING EVERY PAIR?
During a merge, why can you count len(L) − i inversions in one step when you take a value from the right half?
The left half is sorted. If R[j] is smaller than L[i], then because everything from L[i] onward is ≥ L[i], all of them are also greater than R[j] — and each sits at an earlier original position, so each is a genuine inversion with R[j]. That lets you add all len(L) − i of them at once instead of comparing individually. Sortedness is what converts a per-pair count into a per-step count, which is the entire reason merge sort can count inversions in O(n log n).
Merging left half [2, 3, 5] with right half [1, 4, 6], how many cross-inversions are counted, and at which steps?
Four. Taking R[0] = 1 first jumps it ahead of all three left values 2, 3, 5 — that is +3. Then 2 and 3 are taken from the left (no inversions), and taking R[1] = 4 jumps it ahead of the one remaining left value 5 — that is +1. Total 4, and the merged result is [1, 2, 3, 4, 5, 6]. Step the MECHANISM slide and it asks you, at each comparison, whether taking the right value adds inversions.
Why count inversions inside a merge sort at all, rather than with a simpler structure?
Merge sort gives the sortedness the count needs, for free. The bulk count only works because each half is already ordered when the merge runs, and merge sort produces exactly that ordering as a side effect of doing its job. So the counter rides along at no extra asymptotic cost. The other standard O(n log n) approach is a Binary Indexed (Fenwick) tree over value ranks, which trades the recursion for a running frequency structure — worth knowing both exist, because the merge version is easier to reason about and the Fenwick version generalises to online queries.
Piggyback a counter onto merge sort. During a merge, the moment you take a value from the right half before the left half is exhausted, every remaining left value is larger — the left half is sorted — so each forms an inversion with it. That is +(len(L) − i) inversions counted in a single step, which is exactly why the whole thing is O(n log n) instead of the O(n²) of checking every pair.
Reverse Pairs is Count Inversions with one word changed — the condition is a[i] > 2·a[j] instead of a[i] > a[j] — and that one word forces a real structural change. The doubled threshold does not line up with the merge's own comparison, so you cannot count while merging. Instead you count in a separate pass over the two sorted halves first, then merge normally. Because both halves are sorted, a single non-resetting pointer keeps that pass linear.
WHY CAN'T YOU COUNT REVERSE PAIRS DURING THE MERGE, THE WAY YOU COUNT INVERSIONS?
Why must reverse pairs be counted in a separate pass rather than during the merge, the way inversions are?
The two conditions are different relations. Counting inversions works during the merge because “a[i] > a[j]” is exactly the comparison the merge already makes, so each merge decision is a countable event. But a[i] > 2·a[j] is a stricter, different test — a value can satisfy the merge's ordering yet still be a reverse pair, or vice versa. So you sweep the halves once to count under the doubled condition, then merge them with the ordinary comparison. Two different relations need two separate walks.
For sorted left [6, 9, 11] and right [1, 3, 10], the j pointer sweeps the right half. How many reverse pairs, and why does j never move backward?
Five. For L[0] = 6: 6 > 2·1 holds but 6 > 2·3 fails, so j stops at 1 → +1. For L[1] = 9: 9 > 2·3 = 6 holds, j advances to 2 → +2. For L[2] = 11: still 11 > 6, j stays at 2 → +2. Total 5. Because the left half is sorted, each larger L[i] can only satisfy the condition for more right values, so j only ever moves forward — which is what keeps the counting pass O(n) rather than O(n²).
This counts with a[i] > 2 * a[j] in int arithmetic. It passes the samples and fails a hidden test. Why?
while (j <= hi && a[i] > 2 * a[j]) // int overflow near 1e9 j++;
2 * a[j] overflows. LeetCode 493 allows values up to 2³¹−1, so doubling one near that limit wraps to a negative number in 32-bit arithmetic — and then a[i] > (negative) is true for essentially everything, wildly over-counting on exactly the large inputs the samples do not include. Write a[i] > 2LL * a[j] so the doubling happens in 64 bits. Dividing instead — a[i] / 2 > a[j] — is the wrong fix: integer division truncates and drops genuine pairs, which is this deck's TRAP slide.
Reverse Pairs asks for a[i] > 2·a[j], and that doubled threshold does not line up with the merge's ordinary comparison — so the counting is a separate pass before the merge. Both halves are sorted, so a single j pointer sweeps the right half as i advances and never resets: a larger a[i] can only push j further right, which keeps the pass O(n).
“Count pairs i < j with a[i] > 2·a[j]” at n ≤ 5×10⁴. Two things fire together: it is a count over pairs respecting original order (so a global sort is illegal — it would count pairs that never existed), and the bound forbids the O(n²) double loop. That combination is the signature of counting inside merge sort, where the sort happens but the count is taken while the halves are still positionally separated.
It is Count Inversions with the condition a[i] > 2·a[j]. Because the doubled threshold does not match the merge's own comparison, you count in a separate pass over the two sorted halves before merging: for each left value, advance a right pointer while a[i] > 2·a[j] and add how far it reached. The left half being sorted means that pointer never resets, so the pass is linear; then you merge normally and let the recursion sum the counts from every level.
// Count Inversions with the condition a[i] > 2*a[j]. That doubled test // does NOT match the merge comparison, so count in a SEPARATE pass first, // then merge normally. j never resets -> the pass is O(n). 2LL avoids overflow. int countPairs(vector<int>& a, int lo, int mid, int hi) { int cnt = 0, j = mid + 1; for (int i = lo; i <= mid; i++) { while (j <= hi && a[i] > 2LL * a[j]) j++; // 64-bit doubling cnt += j - (mid + 1); // j only moves forward } return cnt; // then merge a[lo..hi] normally } int sortCount(vector<int>& a, int lo, int hi) { if (lo >= hi) return 0; int mid = (lo + hi) / 2; int c = sortCount(a, lo, mid) + sortCount(a, mid + 1, hi); c += countPairs(a, lo, mid, hi); merge(a, lo, mid, hi); // ordinary merge return c; }
// Count Inversions with the condition a[i] > 2*a[j]. That doubled test // does NOT match the merge comparison, so count in a SEPARATE pass first, // then merge normally. j never resets -> the pass is O(n). (long) avoids overflow. int countPairs(int[] a, int lo, int mid, int hi) { int cnt = 0, j = mid + 1; for (int i = lo; i <= mid; i++) { while (j <= hi && a[i] > 2L * a[j]) j++; // 64-bit doubling cnt += j - (mid + 1); // j only moves forward } return cnt; // O(n) across the block }
# Count Inversions with the condition a[i] > 2*a[j]. That doubled test # does NOT match the merge comparison, so count in a SEPARATE pass first, # then merge normally. j never resets -> the pass is O(n). # (Python ints are unbounded, so the C++ 2LL overflow trap cannot bite.) def reverse_pairs(nums): def sort_count(a): if len(a) <= 1: return a, 0 m = len(a) // 2 L, cl = sort_count(a[:m]); R, cr = sort_count(a[m:]) cnt, j = 0, 0 for x in L: # separate counting pass while j < len(R) and x > 2 * R[j]: j += 1 cnt += j # j never resets merged = sorted(L + R) # ordinary merge return merged, cl + cr + cnt return sort_count(nums)[1]
Doubling in 32-bit arithmetic. 2 * a[j] with a[j] near 2³¹−1 overflows and wraps negative, so the comparison is true for almost everything and the count explodes — but only on the large values the samples omit. Write 2LL * a[j]. The tempting “fix” of comparing a[i] / 2 > a[j] is also wrong: integer division truncates, so 5 / 2 = 2 is not > 2 and a real pair (5, 2) goes uncounted. Keep the multiplication and widen it.
The walkthrough for #07 Reverse Pairs. Watch it, then go straight back and write it yourself.
“Maximum product subarray” looks like Kadane and refuses to be Kadane, for one reason: a deeply negative running product becomes the largest the instant it meets another negative. So a single running best is not enough — you have to carry both a running max and a running min ending at each position, and when the next value is negative you swap them, because multiplying by a negative turns the smallest into the largest. The running min is not bookkeeping; it is a live candidate for the answer.
WHY DOES MAXIMUM PRODUCT NEED A RUNNING MINIMUM WHERE KADANE NEEDED ONLY A MAX?
Why is a single running maximum, as in Kadane, insufficient for maximum product?
A negative times a negative is a big positive. Suppose the smallest product ending here is −48. On its own it is useless for a maximum — but if the next element is −2, then −48 × −2 = 96, likely the largest product you have seen, and it was only reachable through the minimum. So you must track the running min precisely so it is available to become the max one step later. In Kadane's world (sums) a negative running value can never help, so one variable suffices; under multiplication it can, which is the whole reason this is a distinct problem.
On [2, 3, -2, 4], what is the maximum product, and where does the running min matter?
6, from [2, 3]. After the first two elements max is 6. At −2, max and min swap and then max becomes max(−2, 6·−2) = −2 while min becomes min(−2, 6·−2) = −12. At 4, max becomes max(4, −2·4) = 4 and the running min −12 stands ready in case a later negative flips it large. Here no later negative arrives, so the answer stays 6 — but the machinery to keep −12 around is exactly what a problem like [−2, 3, −4] (answer 24) depends on.
This multiplies before swapping on a negative. On [-2, 3, -4] it returns 12 instead of 24. Which line is misordered?
int v = a[i]; mx = max(v, mx * v); mn = min(v, mn * v); if (v < 0) swap(mx, mn); // swap AFTER — too late
The swap has to precede the multiplications. When v is negative, the value that should seed the new max is the old min — so you must swap mx and mn first, then compute mx = max(v, mx·v) using the swapped values. Swapping afterward multiplies with the pre-swap max and min, so both new values are computed from the wrong predecessors and the −4 never combines with the stored −6 to make 24. The order is the algorithm: swap on sign, then extend.
Kadane cannot be reused directly: a deeply negative running product becomes the largest the instant it meets another negative. So carry both a running max and a running min ending here, and when the next value is negative, swap them first — the old min is about to become the new max. The running min is not bookkeeping; it is a live candidate for the answer.
“Maximum product of a contiguous subarray” — the word product against the familiar sum is the entire signal. It looks like Kadane and is not, because sign matters: a negative flips the ordering of products, so the smallest running value is a candidate for the largest. Contiguous still means one pass and O(1) space, but the state you carry doubles.
Carry two running quantities ending at the current position: the maximum product and the minimum product. When the next element is negative, multiplying flips their roles, so swap max and min before extending. Then update each with max/min(v, running·v), which also handles a zero cleanly — it resets both to the current value. The answer is the largest max seen anywhere; the running min exists purely so it is ready to become the max after the next negative.
// Not Kadane: a very negative product becomes the LARGEST the instant it // meets another negative. So carry both a running max and min, and swap them // BEFORE multiplying whenever v is negative. The min is a candidate, not noise. int maxProduct(vector<int>& a) { int mx = a[0], mn = a[0], best = a[0]; for (int i = 1; i < a.size(); i++) { int v = a[i]; if (v < 0) swap(mx, mn); // sign flip: swap FIRST mx = max(v, mx * v); // zero resets both to v for free mn = min(v, mn * v); best = max(best, mx); } return best; }
// Not Kadane: a very negative product becomes the LARGEST the instant it // meets another negative. So carry both a running max and min, and swap them // BEFORE multiplying whenever v is negative. The min is a candidate, not noise. public int maxProduct(int[] a) { int mx = a[0], mn = a[0], best = a[0]; for (int i = 1; i < a.length; i++) { int v = a[i]; if (v < 0) { int t = mx; mx = mn; mn = t; } // sign flip: swap FIRST mx = Math.max(v, mx * v); // zero resets both to v for free mn = Math.min(v, mn * v); best = Math.max(best, mx); } return best; }
# Not Kadane: a very negative product becomes the LARGEST the instant it # meets another negative. So carry both a running max and min, and swap them # BEFORE multiplying whenever v is negative. The min is a candidate, not noise. def max_product(a): mx = mn = best = a[0] for v in a[1:]: if v < 0: mx, mn = mn, mx # sign flip: swap FIRST mx = max(v, mx * v) # zero resets both to v for free mn = min(v, mn * v) best = max(best, mx) return best
Swapping max and min after the multiplications instead of before. On a negative element the new max should be built from the old min, so the swap must precede both updates; swapping afterward computes both values from the wrong predecessors and quietly loses products like the 24 in [−2, 3, −4]. The second trap is initialising best = 0 — same mistake as Kadane, and it returns 0 on an all-negative single element such as [−3], where the answer is −3.
The walkthrough for #08 Maximum Product Subarray. Watch it, then go straight back and write it yourself.
“Count pairs i < j with a[i] > 2·a[j]”, n ≤ 5×10⁴. Why can this not be done with two pointers on the sorted array, the way 3Sum is?
Sorting destroys the index relation. 3Sum asks for values and does not care where they came from, so sorting is free. Reverse Pairs asks about pairs in original order, so a global sort would count pairs that do not exist. Merge sort threads the needle: it sorts, but it counts at each merge — at the moment the two halves are still positionally separated, so every pair counted genuinely has i in the left half and j in the right. That is why the counting must happen inside the recursion and not after it.
Maximum Product Subarray tracks a running minimum alongside the maximum. What exactly does the minimum buy you?
Multiplying by a negative swaps the roles. If the running minimum is −48 and the next value is −2, the product is +96 — the largest thing you have seen, and it was reachable only through the minimum. So at every step you compute both candidates and, when a[i] < 0, swap them before extending. This is why Max Product is not a small edit of Kadane despite the family resemblance: the loop body carries two quantities and a conditional swap.
Every one of these compiles, runs, and returns something reasonable-looking. Four of them only fail on the large tests, which is the worst possible place to find out. A crash teaches itself; a silent wrong answer costs an hour.
Majority II's two survivors are only the only possible answers, never proof that either occurs more than ⌊n/3⌋ times. On [1,2,3] the algorithm confidently proposes two candidates and the correct answer is the empty list. The second counting pass is not optional here — it is the algorithm.
3Sum needs a skip for the fixed index and for both pointers after a hit. Skipping only the fixed one emits duplicate triplets; skipping before recording loses valid ones. Every triplet you output is individually correct, so the bug looks like a judge problem.
Four values near 10⁹ exceed INT_MAX and wrap negative, so the sum compares as below target and lo advances when it should not. You get a short answer list on the large tests only.
Dividing to avoid overflow truncates: with a[i]=5, a[j]=2, 5/2 = 2 is not > 2, so a genuine reverse pair goes uncounted. Compare a[i] > 2LL * a[j] instead. Off by a handful on big inputs — never on your examples.
The count must run as a separate pass over the two halves before merging. Folding it into the merge comparison ties the counting pointer to the merging pointer, and the count comes out low. Both loops are O(n), so the separate pass costs nothing.
last[1] = cur[1] looks right and shrinks the kept interval whenever a short interval sits entirely inside a long one — [15,18] then [16,17] yields [15,17]. Write max(last[1], cur[1]).
Seven compositions, eight problems. The right-hand column is the part that matters — by this point the algorithms are known and only the recognition is hard.
Nothing in this deck was a new idea, and that is the point worth carrying forward: hard problems are compositions. When the next one looks unfamiliar, the useful question is not “what trick is this” but “which two things is this”.
Lectures are Striver's A2Z DSA course. Problem links are LeetCode. 8 units from 8 of the playlist's 28 lectures; rows 1–18 are deck 1.
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.