Sweep Line And Sliding Window Optimization

What's being tested

These problems test mastery of sweep line and sliding window patterns: converting interval/overlap problems to event scans and optimizing contiguous-subarray/string constraints with two pointers. Interviewers probe correctness on endpoint semantics, aggregate maintenance, and asymptotic tradeoffs (e.g., O(n) vs O(n log n)).

Patterns & templates

• Sweep line via event sorting — convert starts/ends to +1/−1 events, sort O(n log n), single pass accumulates active count, track maximum.

• Sliding window two-pointer on contiguous arrays/strings — expand right, contract left, maintain window invariant; typical runtime O(n), space O(1).

• Prefix sums for frequent range-sum queries: preprocess O(n), answer in O(1); be explicit about inclusive/exclusive indexing.

• Use a heap/multiset to track active endpoints when you must remove arbitrary intervals; updates cost O(log n).

• Monotonic queue (deque) for window min/max to get amortized O(n) for extremal queries inside sliding windows.

• For string merging, use a deque/string builder to avoid repeated O(n^2) concatenation; maintain indices rather than slicing.

• Always normalize timestamps/endpoints (inclusive vs exclusive) and tie-break consistently when sorting events.

Common pitfalls

Pitfall: Off-by-one errors from unclear inclusive/exclusive endpoint rules — clarify and normalize before coding.

Pitfall: Naive concatenation in loops yields O(n^2) time; use builders or index-based merging.

Pitfall: Forgetting to handle identical timestamps (start and end same time) — decide ordering (end before start or vice versa) and document it.

Practice these

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