Sliding Window And K-Flip Optimization

What's being tested

Candidates must recognize how to reduce a limited-flip optimization into a sliding window / two-pointer decision problem and reason about gains per flip. Interviewers probe algorithmic translation (map flips to added value), correctness across edge cases, and an O(n) time / O(1) extra-space implementation.

Patterns & templates

• Convert inputs to a gain array: map each day to its base pay and extra gain if flipped; then reason about contiguous windows.

• Two-pointer sliding window: expand right, track zeros/flips used, shrink left when flips > k; overall O(n) time, O(1) space.

• Maintain running window sum rather than recomputing; update in O(1) when pointers move to keep total pay.

• Use prefix sums to evaluate arbitrary window sums in O(1) if you need random-access checks or binary search.

• Binary-search-on-answer: when feasibility is monotonic (e.g., can we achieve at least X pay?), combine O(n) check with O(log M) search for O(n log M).

• Edge-case fast path: if k >= total rest-days (or flips can cover all negatives), return full-sum immediately to avoid unnecessary logic.

Common pitfalls

Pitfall: forgetting to include the original pay of already-working days when computing the post-flip total (only adding flipped gains is wrong).

Pitfall: off-by-one in window boundaries — ensure left pointer moves before reducing flips count when leaving a flipped/rest day.

Pitfall: not handling k >= count of rest days; algorithm should short-circuit to full-sum to avoid incorrect window math.

the practice cards below cover the canonical variants — solve all of them and time yourself