10 Cross-Topic Lessons from a 123/138 LeetCode Sprint

I first published this retrospective 46 problems into a 12-week DSA sprint. My tracker is now at 123 / 138 slots: I have worked through Week 11 and am 2 / 12 into Week 12. The tracker deliberately repeats a few problems across topics, so 123 is a progress metric—not a claim of 123 unique accepted problems.

The expanded tracker did not produce dozens of unrelated tricks. It made the same failures show up in new disguises. A bad state definition in dynamic programming felt a lot like an under-specified sliding window. Marking a BFS node too late felt like inserting into a hash map too early. A wrong heap invariant looked suspiciously like a wrong binary-search invariant.

These are the ten lessons that survived that repetition. The bugs below are not hypothetical warnings. They are mistakes I wrote, plus the smallest counterexamples that finally made the mistake obvious.

1. If I cannot define the state in one sentence, I am not ready to update it

My first House Robber state was internally inconsistent:

dp[1] = nums[1]
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])

The initialization says dp[1] means “money from robbing house 1.” The recurrence needs it to mean “the best result using houses 0 through 1.” Those are different contracts.

The counterexample is [2, 1, 1, 2]. Initializing dp[1] = 1 permanently loses the valid choice of taking the first house. The recurrence returns 3 instead of 4. I added a separate vmax to patch the output, but the wrong state had already contaminated later states. A downstream maximum could not repair an upstream definition.

The correct base case has the same meaning as the recurrence:

prev2 = nums[0]
prev1 = max(nums[0], nums[1])

for x in nums[2:]:
    prev2, prev1 = prev1, max(prev1, prev2 + x)

The same lesson appeared outside DP:

• In Fruit Into Baskets, I stored only the kinds of fruit in a deque. That could not answer “when has this kind completely left the window?” The input [1,1,1,2,3,3] exposed it: my window kept three kinds and reported 5 instead of 4. The state needed counts, not just names.
• In Maximum Product Subarray, keeping only the largest product ending here loses a negative value that may become the next maximum. For [2,-5,-2,-4,3], the state must retain both the current maximum and minimum to recover the answer 24.
• In Longest Palindromic Substring, one left endpoint per right endpoint is not enough. Palindromicity depends on both boundaries, so the state naturally becomes dp[left][right].

My current rule is simple: finish the sentence “this state contains exactly…” before writing an update. If I need a patch variable later, I first suspect that sentence.

2. The empty state is data, not a special case

Prefix sums taught me to put prefix[0] = 0 in front. Later topics made the idea more general: the empty state should be represented by the identity that cooperates with the operation.

Operation	Empty-state value	Why it works
Sum	0	x + 0 = x
Product	1	x * 1 = x
Minimum	inf	a real candidate always beats it
Maximum	-inf	a real candidate always beats it
Counting-DP empty choice	1	there is exactly one way to choose nothing
Unreachable count	0	no valid construction has reached this state
Prefix-frequency count	{0: 1}	one empty prefix exists
Earliest prefix index	{0: -1}	the empty prefix ends before index 0

One of my earliest versions used an inclusive prefix array, appended a zero at the end, and relied on Python's negative indexing:

return prefix[right] - prefix[left - 1]  # left == 0 reads prefix[-1]

It passed, but only because prefix[-1] wrapped around to the hidden zero. The same code is an out-of-bounds bug in languages without negative indexing. The honest form is:

prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)

return prefix[right + 1] - prefix[left]

Coin Change exposed the other half of the rule. I used -1 for “unreachable” while minimizing. Then unreachable states won every min, and -1 + 1 created fake zero-cost solutions. With coins = [2,3] and amount = 4, that version returned 0 instead of 2.

Internally, inf is the right value because it composes safely:

dp = [float("inf")] * (amount + 1)
dp[0] = 0

for a in range(1, amount + 1):
    for coin in coins:
        if coin <= a:
            dp[a] = min(dp[a], dp[a - coin] + 1)

return -1 if dp[amount] == float("inf") else dp[amount]

The external API may require -1. That does not mean -1 belongs inside the recurrence. I now separate the algorithm's internal algebra from the return-value protocol, and translate only at the exit.

3. Update order is part of the algorithm

Two adjacent lines are not interchangeable just because both eventually run.

In prefix-sum counting, the map is a record of the past. I must query it before the current prefix joins that past:

prefix += x
answer += seen.get(prefix - k, 0)       # query history
seen[prefix] = seen.get(prefix, 0) + 1  # then become history

If I insert first, the current prefix can match itself. For Subarray Sum Equals K with nums = [1,-1] and k = 0, the correct answer is 1; inserting first counts two zero-length “subarrays” as well and returns 3.

The same ordering constraint reappeared in three different tools:

• BFS: mark a node when it enters the queue, not when it leaves. Otherwise several parents can enqueue the same node before its first dequeue.
• Union-Find cycle detection: ask whether find(u) == find(v) before union. If I union first, the condition is true for every edge. On [[1,2],[2,3],[3,1],[3,4]], the redundant edge is [3,1], not the first or last edge by accident.
• Compressed 0/1 knapsack: iterate capacity backward. With one item 2 and target 4, a forward scan sets dp[2] and then reuses that freshly written value to set dp[4]—using the same item twice.

These are all temporal invariants. “Seen” means seen before now. “Already connected” means connected before this edge. “Previous row” means the state before this item. Moving a line changes that meaning, even when the variables have the same names.

4. Every destructive move needs a proof

Popping a stack entry, advancing a pointer, pruning a branch, and moving a binary-search boundary all destroy candidates. Before doing any of them, I now ask:

What fact proves this candidate can never be the answer?

My rotated-array minimum passed tests with two overlapping safety nets: an early “peek at the previous element” return, plus a final fallback. The loop itself used right = mid - 1 even when mid could still be the minimum. Delete either safety net and the code quietly breaks.

The clean invariant keeps mid whenever it may still be the answer:

left, right = 0, len(nums) - 1
while left < right:
    mid = (left + right) // 2
    if nums[mid] > nums[right]:
        left = mid + 1   # mid is provably not the minimum
    else:
        right = mid      # mid may be the minimum, so keep it
return nums[left]

Container With Most Water gave me the same lesson in greedy form. I tried moving both ends when neither immediate next move improved the current area. On [5,1,100,50], that jumps past the optimal pair (100,50) with area 50.

The valid greedy move is not “take the next thing that looks better.” It is “discard the shorter wall because every narrower container that keeps it is capped by the same short wall.” That is a domination proof.

Longest Increasing Subsequence exposed the distinction between pop and replace. Treating its tails array like a monotonic stack and popping larger endings destroys the historical fact that a subsequence of that length has existed. For [2,3,1,4], popping gives length 2 instead of 3. The correct operation replaces exactly one threshold—the first value greater than or equal to the new number—without erasing longer records.

The syntax is tiny; the proof is the algorithm.

5. Constraints are algorithm instructions

I used to read constraints after understanding the problem. Now I read them as a list of approaches the problem setter is trying to kill.

• “O(log n) required” killed my “binary search, then expand left and right” solution for finding a target range. On [8,8,8,8,8], the expansion is linear. The answer needs two boundary searches.
• “The array may contain negatives” kills a sum-based sliding window because the window sum is no longer monotone. Prefix sum plus a hash map survives.
• “O(n) required” in Longest Consecutive Sequence kills sorted(set(nums)). Sorting gets the right result in O(n log n) but misses the point; scanning only from values whose predecessor is absent gives linear total work.
• Coordinates up to 10^9 or 2^31 - 1 kill per-coordinate arrays and loops. I tried a difference array for Interval List Intersections and a coordinate-by-coordinate loop for Skyline. One wants impossible memory; the other can run for billions of empty positions. The right iteration domain is intervals or event points, not the numeric axis.

This question has become part of my pre-code checklist:

Which obvious solution is this constraint designed to exclude?

It catches complexity bugs before a correct-looking implementation makes them harder to notice.

6. When many searches share a destination, reverse the search

Several graph problems became simple only after I stopped searching from every unknown point.

• Surrounded Regions is awkward as “which regions are enclosed?” It becomes easy as “which O cells can the boundary reach?” Mark those safe cells, then flip the rest.
• Pacific Atlantic Water Flow is expensive as “can this cell flow to each ocean?” Reverse the edges: start from both oceans and climb to cells of equal or greater height. The answer is the intersection of the two reachable sets.
• 01 Matrix asks every cell for its nearest zero. Put all zeros into one queue at distance 0 and expand once.
• Rotting Oranges asks how simultaneous infection spreads. Put all rotten oranges into the initial queue; one BFS layer is one minute.

The shared template is small:

queue = deque(all_states_with_known_answer)
mark_all_as_seen(queue)

while queue:
    state = queue.popleft()
    for nxt in reverse_or_outward_neighbors(state):
        if nxt not in seen:
            answer[nxt] = answer[state] + 1
            seen.add(nxt)
            queue.append(nxt)

Running one BFS per source repeats the same regions. A multi-source BFS is not merely an optimization; it models simultaneous expansion correctly.

I now look for phrases such as “nearest source,” “eventually reaches a boundary,” or “all sources spread at once.” They often mean: start from the states whose answers are already known and propagate outward.

7. The lifetime of visited depends on the question

I once treated “mark visited” as a generic graph rule. Backtracking showed why that is incomplete.

For flood fill, the question is about nodes: “which cells belong to this component?” Once a cell is processed, visiting it again has no value. The mark is permanent.

For Word Search or permutations, the question is about paths: “which choices form this particular solution?” A cell or item may be used by a different sibling path. The mark must live only for the current recursive frame:

path.append(choice)
used[i] = True

backtrack()

used[i] = False
path.pop()

Leaving out the restoration does not just leak state; it permanently blocks legal sibling branches and creates false negatives.

I hit the companion bug in Subsets:

answers.append(path)     # stores the same mutable list object

After recursion unwound, every entry referred to the same now-empty list. The fix is a snapshot:

answers.append(path[:])

This also explains why “generate everything, then deduplicate” is usually a smell. My first subset approach generated both [1,2] and [2,1] and tried to filter afterward. A start index makes the invalid ordering impossible to generate. For duplicate values, sorting plus same-level pruning gives each result one canonical path.

The rule I keep now is:

• Enumerating nodes: mark permanently.
• Enumerating paths: mark on entry, restore on exit.
• Saving a mutable path: copy at the moment it becomes a result.

8. A recursive function can return one value and build another answer

Tree diameter initially tempted me into two recursive functions: compute a node's height, then recursively compute diameters and call height again at every node. The logic is correct; on a skewed tree the repeated height work makes it O(n^2).

One postorder traversal can produce two different quantities:

best = 0

def height(node):
    nonlocal best
    if not node:
        return 0

    left = height(node.left)
    right = height(node.right)

    best = max(best, left + right)  # answer using both branches
    return 1 + max(left, right)     # value one parent can extend

The distinction is structural. A path that continues to the parent can use only one child branch. A path whose highest point is the current node can join both.

Maximum Path Sum uses the same skeleton:

• return the best one-sided gain to the parent;
• update a global best with left + node + right;
• clamp negative child gains to zero.

Its smallest counterexample is also its most important initialization test: a one-node tree [-3]. Initializing the global answer to 0 returns a path that does not exist. It must start from a real node value or -inf.

Minimum Depth delivered a related warning about base cases. Replacing max with min in the maximum-depth recurrence fails on [1,None,2]: the nonexistent left branch contributes 0 and wins, producing depth 1 instead of 2. An identity that is harmless under one aggregation can poison another.

I now write down two contracts for recursive tree problems: what this call returns upward, and what candidate answer this node contributes globally.

9. Graph modeling happens before DFS, BFS, or Union-Find

The hardest part of several graph problems was choosing what a node meant.

In Bus Routes, counting station-to-station edges answers the wrong question. The cost is buses boarded, so a BFS layer must represent one additional route. The useful index is stop -> routes containing that stop, with separate visited sets for stops and routes.

In Accounts Merge, my account-to-account model was correct but expensive: compare every pair of accounts for shared email, then union matching accounts. That is O(n^2) before considering set intersections.

The cleaner model makes emails the nodes. Union all emails within each account. If an email appears in two accounts, it is literally the shared node that joins the components. The pairwise comparison disappears.

The same modeling question showed up elsewhere:

• Word Ladder nodes are words; edges are one-character changes.
• Open the Lock nodes are four-digit strings; edges are one wheel turn.
• Clone Graph is primarily an old_node -> new_node mapping problem; DFS versus BFS is secondary.
• In grid Union-Find, (row, col) becomes row * width + col, but boundary checks must still happen in two dimensions. Checking only the flattened id lets the right edge wrap into the next row.

Before choosing a traversal, I now ask three questions:

1. What exactly is a node?
2. What operation creates an edge?
3. What does one unit of cost or one BFS layer mean?

Getting those right often makes the algorithm routine. Getting them wrong can make a correct traversal solve a different problem.

10. Keep the unresolved frontier, not the whole history

My best heap improvements came from asking what must be eligible right now.

For Merge K Sorted Lists, I first pushed every node and used the list index as a tuple tie-breaker. One list containing [1,1,2] breaks it: equal values from the same list also share the same list index, so Python eventually tries to compare two ListNode objects and raises TypeError.

The better invariant is:

The heap contains at most one node from each list: that list's smallest unresolved node.

Pop one node, then push its successor. Now the list index is unique within the heap, the heap size stays at most K, and the complexity becomes O(N log K) instead of sorting all N nodes.

IPO exposed the same frontier bug in a different form. I rescanned every project on every round and reinserted affordable projects, so the same project could be completed twice. With k = 2, w = 0, profits [1,2], and capital [0,3], my version earned the first project's profit twice and returned 2; the correct answer is 1.

Sorting projects by capital and advancing a pointer fixes the lifecycle:

• each newly affordable project enters the profit heap once;
• unchosen affordable projects stay eligible in the heap;
• the chosen project leaves once;
• the pointer never moves backward because capital never decreases.

The same skeleton later powered offline interval queries and Skyline: sort by the condition that unlocks a candidate, advance one-way, keep active candidates in a heap, and lazily remove candidates only when they can affect the top.

A heap is not a bag of everything I have seen. A monotonic stack is not a bag of previous indices. They are compressed representations of the unresolved frontier. If I cannot state exactly why every stored item is still eligible, I probably do not yet have the invariant.

---

The meta-lesson

At 46 problems, I thought my bugs lived in edge cases around otherwise-correct algorithms. At 123 tracker slots, I think that distinction is mostly false. The “edge” details are the algorithm:

1. What does the state mean?
2. How is the empty state represented?
3. In what order do reads, writes, marks, and moves happen?
4. What proof allows a candidate to be discarded?
5. Which approach does a constraint rule out?
6. Can the search run backward from known answers?
7. How long should a visited mark live?
8. What returns to the parent, and what updates the global answer?
9. What are the graph's actual nodes and edges?
10. What exactly belongs in the unresolved frontier?

The most useful part of my notes is still the same as it was in the first version: every problem gets a “bug I actually wrote” and a counterexample. The fix tells me how to pass one test. The counterexample tells me which assumption was false—and that is the part that transfers to the next topic.

What mistake has followed you across the largest number of seemingly unrelated problems?