Week 07 — Prefix Sums + Binary Search: The Logarithmic Mindset

Phase: Month 02 — Patterns Theme: Two pillar techniques: turn “range sum in O(1)” into a habit (prefix sums), and learn to invent a monotone predicate so binary search applies (rotated arrays, partition-on-answer). Difficulty: Medium → Hard. p35 is one of the most-feared LC Hards; we’ll tame it.

Week Goals

By end of week, you should:

1. Reach for a prefix sum the moment you see “subarray sum” or “range sum” — no exceptions.
2. Recognize prefix[j] - prefix[i] == k as the canonical hashmap reduction.
3. Write binary search on rotated arrays without confusing yourself — three pivots, one invariant.
4. Articulate the difference between “binary search on indices” (p33, p34) and “binary search on partitions” (p35).
5. Defend complexity proofs for O(log(min(m,n))) Median of Two Sorted Arrays.

Problem Table

Daily Schedule (suggested)

• Mon — p31 Subarray Sum K. The “prefix sum + hashmap” pattern. Internalize the negative-numbers case (sliding window does NOT work here).
• Tue — p32 Range Sum Query 2D. 2D extension of prefix sum. Inclusion-exclusion.
• Wed — p33 Search in Rotated Sorted Array. The classic. Know the “which half is sorted?” invariant.
• Thu — p34 Find Minimum in Rotated Sorted Array. Variant of p33; tighter invariant on the pivot.
• Fri — p35 Median of Two Sorted Arrays. The Hard. Binary search on partition. Block 90+ minutes.
• Sat — Re-solve all five from memory under timer. Mock yourself.
• Sun — Spaced repetition: revisit Week 1 (p01) and Week 4 (Trees) and Week 6 (p30). 30 min total.

Readiness Gate (must pass to advance)

• Can write Subarray Sum K (with hashmap including the count[0]=1 seed) in under 8 min.
• Can write the 2D prefix sum with inclusion-exclusion (both build and query) in under 12 min.
• Can write Search in Rotated Sorted Array WITHOUT looking up the “which half is sorted” decision in under 15 min.
• Can write Find Minimum in Rotated Sorted Array in under 10 min — and explain why <= hi vs < hi matters.
• Can sketch Median of Two Sorted Arrays binary-search-on-partition in 30 min with the partition invariant correctly stated.
• All 15 files commit-ready: every solution.py ends with ALL TESTS PASSED.

Anti-Pattern Hit-List

1. Sliding window on Subarray Sum K with negatives — the monotone property fails. Use prefix sum + hashmap.
2. Forgetting count[0] = 1 in the Subarray Sum K hashmap seed — misses subarrays starting at index 0.
3. Building 2D prefix sum with off-by-one indices — always allocate (R+1) x (C+1) with a zero border to avoid edge-case branches.
4. Rotated binary search: comparing nums[mid] to nums[hi] vs nums[lo] inconsistently — pick ONE side and stick with it. Comparing to nums[hi] is more robust for both p33 and p34.
5. Rotated binary search with lo <= hi — for “find pivot” style (p34) you want lo < hi so loop ends with lo == hi == answer.
6. Median of Two Sorted Arrays: binary search over the larger array — you must binary-search the SMALLER. Otherwise the partition index can go out of bounds for the larger.
7. Median: hardcoding “odd vs even” branches inside the loop — compute once at the end using the four partition values.
8. Treating Hard problems as off-limits — p35 is hard but learnable in one focused sitting.

Connections to Phase Labs

• phase-02-patterns/labs/lab-03-prefix-sums.md — exactly this week.
• phase-02-patterns/labs/lab-04-binary-search-on-answer.md — preview of “binary search where the array isn’t the input” — p35 is a relative.
• phase-01-foundations/labs/lab-07-binary-search-fundamentals.md — refresh the basics before p33-p35.

Stretch (if you finish early)

• LC 1248 — Count Number of Nice Subarrays (prefix sum on parity counts).
• LC 974 — Subarray Sums Divisible by K (prefix sum mod K — note Python’s correct negative-mod handling).
• LC 81 — Search in Rotated Sorted Array II (duplicates — the killer follow-up; worst case O(N)).
• LC 154 — Find Minimum in Rotated Sorted Array II (duplicates — same pattern as LC 81).
• LC 1095 — Find in Mountain Array (interactive binary search, two phases).