Sliding Window, Binary Search, and Prefix Reasoning

What's being tested

These problems test search over structured spaces: contiguous windows, monotonic answer ranges, prefix/suffix constraints, and cumulative sums. Interviewers look for proof that your invariant is correct, not just that you recognize binarySearch() or two pointers.

Patterns & templates

• Sliding window for minimum covering substring — O(n) time with need, have, and formed; contract only while valid.

• Binary search on answer for rates/cuts — define feasible(x) as monotonic; use lo, hi, mid, and justify termination.

• Prefix sums for contiguous partition scoring — precompute prefix[i+1] = prefix[i] + nums[i]; range sum becomes prefix[r] - prefix[l].

• Suffix reasoning for removals/duplicates — scan from the right to find the longest valid suffix, then compute minimum prefix removal.

• Interval merge after sorting — O(n log n) sort by start, then merge if next.start <= cur.end; clarify closed vs half-open intervals.

• Floating-point binary search for geometry — iterate fixed rounds or until eps; avoid equality checks and reason about area monotonicity.

• Kadane-style subarray optimization — track best ending here and global best; handle all-negative arrays without defaulting to zero.

Common pitfalls

Pitfall: Treating binary search as “find exact value” instead of “find boundary”; Google interviewers expect a monotonic predicate and invariant.

Pitfall: Shrinking a sliding window before all required character multiplicities are satisfied; distinct-count logic is not enough.

Pitfall: Forgetting edge cases: empty arrays, duplicate intervals, impossible coverage, all-negative sums, and precision tolerance for geometry.