Sequence Optimization With Limited Flips

What's being tested

Requires converting a constraint ("flip at most k rest days") into an algorithmic pattern that maximizes a numeric objective under limited operations. Interviewer checks for recognizing a sliding window/two-pointer reduction or a prefix-sum + greedy approach, implementing it in O(n) or O(n log n), and reasoning about edge cases (exact vs up-to-k flips, negative/zero weights).

Patterns & templates

• Sliding window on contiguous intervals: expand/contract while tracking flipped-rest count; yields O(n) time, O(1) extra space.
• Prefix sum for weighted days: precompute cumulative sums to compute any interval sum in O(1) after O(n) setup.
• Two-pointer with count constraint: move right pointer, increment flip count for rest-days, advance left until flips ≤ k.
• Kadane variant with state: keep best subarray ending at i with j flips (small k → DP over flips) — O(n*k) time.
• Greedy + heap: pick top-k rest-day gains if flips need not create contiguity — O(n + k log n) time.
• Handle exact k vs up-to-k: if exact, enforce flipping additional minimal-loss days; if up-to-k, allow fewer flips.
• Watch weights: if daily pay can be negative, convert to max-subarray-with-limited-changes pattern, not plain zero/one.

Common pitfalls

Pitfall: Treating flips as independent gains — forgetting that flipping interior rest days merges paid segments and creates non-additive gains.

Pitfall: Implementing sliding window but not handling "exact k" requirement; off-by-one when left/right pointers move leads to wrong counts.

Pitfall: Using O(n*k) DP without bounding k — declare constraints and switch to heap/greedy when k is large relative to n.

Practice these

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