DEV Community

Xinyang Wu
Xinyang Wu

Posted on

6 Cross-Topic Lessons from Grinding 46 LeetCode Problems

#algorithms #leetcode #python #interview

I'm 46 problems into a 12-week DSA sprint, keeping detailed notes on every bug I actually wrote — not the bugs that could happen, but the ones that did. Six lessons keep reappearing across completely different topics. Here they are, each with the real mistake and the counterexample that exposed it.

1. The sentinel is the identity element of your operation — and it goes in front

Prefix sum arrays use a leading prefix[0] = 0. Prefix product arrays (LeetCode 238) use a leading 1. The hash map in subarray-sum problems (560, 523) seeds with the "empty prefix" entry. These aren't three tricks — they're one trick:

Prefix sum Prefix product Prefix + hash map
Sentinel 0 (additive identity) 1 (multiplicative identity) {0: 1} or {0: -1}
Meaning "sum of an empty range is 0" "product of an empty range is 1" "an empty prefix exists"
Kills which special case left == 0 "no left/right neighbor" "subarray starting at index 0"

The bug I actually wrote: an inclusive prefix sum with the sentinel appended to the end, reached via Python's negative indexing:

def sumRange(self, left, right):
    return self.sum_val[right] - self.sum_val[left - 1]  # left=0 → [-1] → wraps to the appended 0
Enter fullscreen mode Exit fullscreen mode

It passed every test. It's still wrong — a "backdoor sentinel." Any reader sees left - 1 and assumes an off-by-one bug; in C++ or Java it is one. Code that requires extra reasoning just to see why it doesn't crash will get flagged in any review. Put the identity element in front, where the index arithmetic reads naturally: prefix[r+1] - prefix[l].

2. Query before insert

The one-pass hash map pattern (Two Sum, 560) has a strict order: ask the map about your complement first, then insert yourself.

for n in nums:
    bsval += n
    res += beforesum[bsval - k]   # query history first
    beforesum[bsval] += 1         # then join history
Enter fullscreen mode Exit fullscreen mode

Swap those two lines and you match against yourself. For 560 with k = 0 the counterexample is tiny: nums = [1, -1] — correct answer 1, insert-before-query answer 4.

The deeper mental model: a hash map in a scan is a record of the past. "Look at the current element, ask about everything before it." Insert-first corrupts the definition of "before."

3. The requirements are the algorithm hint

Three times now, a constraint I initially read as flavor text was actually the problem telling me which technique to use:

  • "O(log n) required" (LC 34): my first version found the target with binary search, then expanded linearly to find the range boundaries. On [8,8,8,8,8] that expansion is O(n). The requirement existed precisely to exclude my approach. Correct answer: two independent lower-bound searches.
  • "You may not use division" (LC 238): not arbitrary cruelty — the obvious total / nums[i] breaks the moment the array contains a zero. The constraint is the hint: prefix × suffix products.
  • Array may contain negatives (LC 560): silently kills sliding window, because window sums lose monotonicity. Only prefix sum + hash map survives.

New rule: before coding, re-read the constraints and ask "which obvious approach is this constraint designed to kill?"

4. Don't mutate your input, and don't copy it either

Two opposite sins, same root — not respecting the data you were handed.

Mutation (LC 162, peak finding): I appended a -inf sentinel to the input list. Two problems: it's a visible side effect (call the function twice, the list grows twice), and — funnier — tracing the index math showed my sentinel was never read. The -∞ boundary in that problem is a reasoning tool, not a data structure you build.

Copying (LC 704, binary search): recursive binary search with slices:

return binary(n[mid + 1:])   # slices copy: T(n) = T(n/2) + O(n) = O(n)
Enter fullscreen mode Exit fullscreen mode

Logically correct, and the logarithm is gone. The soul of binary search is moving indices over unchanged data. Slicing quietly degrades O(log n) to O(n) — the worst kind of wrong, because every test still passes.

5. Two safety nets over one hole is worse than one

My rotated-array-minimum (LC 153) solution passed, but contained two mechanisms catching the same edge case: a "peek at the neighbor" early return, and a final fallback — because my main loop discarded mid even when mid could be the answer.

Delete either mechanism and it breaks. Keep both and it works — but now the code lies about its own invariant, and the next person to "simplify" it ships a bug.

The honest version needs one rule: never discard an index that might be the answer.

while l < r:
    mid = (l + r) // 2
    if nums[mid] > nums[r]:   # min is strictly right of mid
        l = mid + 1           # mid can't be the answer → safe to discard
    else:
        r = mid               # mid might be the answer → keep it
return nums[l]
Enter fullscreen mode Exit fullscreen mode

One side moves mid ± 1 (provably not the answer), the other stops at mid (possibly the answer). Every binary search variant I've written since reduces to deciding which side gets which.

6. 90% of the bugs live in exactly two places

After enough prefix-sum + hash problems, my bug reports converged: the algorithm is never the problem. The bugs are always in

  1. the sentinel's index, and
  2. the problem's side constraint.

LC 523 (subarray sum divisible by k, length ≥ 2) — I hit both in one submission:

  • Seeded the remainder map with {0: 0} instead of {0: -1}. The empty prefix lives at virtual index -1. Counterexample: nums = [3,3], k = 6 — with -1 the length check gives 1 - (-1) = 2 ✓; with 0 it gives 1, and the answer is wrongly False.
  • Returned True on any repeated remainder, forgetting length ≥ 2. Counterexample: nums = [5,1], k = 5 — the very first element matches the sentinel and returns True for a length-1 subarray.

The template took five minutes. Finding those two counterexamples took the session. Now I write the boundary test cases before the loop body: empty-prefix case, starts-at-zero case, minimum-length case.

The meta-lesson

None of these are about knowing more algorithms. They're about the same three centimeters around the algorithm: what the identity element is, what order state updates happen in, what the constraints quietly forbid, and which index is allowed to be discarded. That's where my actual bugs lived — all of them.

I keep these notes per-topic with a "pitfalls I personally hit" section for every problem. Writing the counterexample down (not just the fix) is what made the patterns visible.

What cross-topic patterns have you noticed in your own grinding? I'd genuinely like to compare notes.

Top comments (0)