Sliding Window

Coding Problems: DSATopic 8 of 197 questions

Q1Fruit Into Baskets / Longest With At Most K Distinct: Variable Window + Char Count

Expand the window and track distinct counts in a map; when distinct exceeds K, shrink from the left until it is at most K again.

Read Answer

Q2Max Consecutive Ones: Longest Run of 1s

Count the current run of ones, update the best, and reset the current run to zero on every zero.

Read Answer

Q3Explain Sliding Window: Fixed-Size vs Variable-Size, Expand Right / Shrink Left

Expand right to add, shrink left to remove, and update the answer incrementally, turning repeated subrange scans into one linear pass.

Read Answer

Q4Sliding Window Maximum: Monotonic Deque Maintaining Decreasing Order

Keep a deque of indices with decreasing values; the front is always the window maximum, and each index enters and leaves at most once.

Read Answer

Q5Max Consecutive Ones III: Sliding Window Allowing At Most K Zero Flips

Slide a window counting zeros; keep it valid while zeros are at most K, and the widest such window is the answer.

Read Answer

Q6Sliding Window Median (Two Heaps with Lazy Deletion)

Two heaps for the window, add the new element, lazily mark the old one, rebalance, and read the median at the boundary.

Read Answer

Q7Sliding Window Maximum: monotonic deque

Maintain a decreasing deque of indices, drop stale indices from the front and smaller indices from the back, and the front is always the window maximum.

Read Answer