Sliding Window
A variable- or fixed-size window over a sequence, expanded and contracted in O(n) total instead of recomputing from scratch.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain why a variable-size sliding window achieves O(n) time despite having two nested-looking pointer movements.(show answer)
Both the left and right pointers only ever move forward, never backward, and each can move at most n times total across the entire scan. Even though the logic alternates between expanding (right) and shrinking (left), the total number of pointer movements across the whole algorithm is bounded by 2n, giving O(n) overall — not O(n) per step, which would make it O(n²).
Q2.Walk through solving "longest substring without repeating characters" with a sliding window.(show answer)
Expand right one character at a time, tracking characters seen in the current window (e.g. in a hash set or a last-seen-index map). If the incoming character is already in the window, shrink from left — removing characters from the set — until the duplicate is gone. Track the maximum window size seen at each step. This solves it in O(n) time instead of checking every substring (O(n²) or worse).
Q3.How does a fixed-size sliding window avoid recomputing an aggregate (like a sum) from scratch at every position?(show answer)
Instead of resumming all k elements at every window position (O(k) per step, O(nk) total), maintain a running aggregate: when the window slides by one, subtract the value of the element leaving on the left and add the value of the element entering on the right — an O(1) update per step, giving O(n) total regardless of window size k.
Q4.Why doesn't sliding window apply to a problem like "find the longest increasing subsequence" (not necessarily contiguous)?(show answer)
Sliding window relies on the elements under consideration being a contiguous range that can be incrementally expanded/shrunk from the ends. A subsequence (not necessarily contiguous) doesn't have this contiguous-range structure — elements can be skipped arbitrarily — so there's no meaningful "window" to slide; a different technique (like dynamic programming) is needed instead.