Picture a train with exactly 3 connected cars, rolling forward one station at a time along a track of 100 stations. At every station, the car at the back detaches and a new one joins at the front, so you always see exactly 3 cars, just a different 3. A sliding window works the same way over an array or a string: a contiguous stretch that grows and shrinks as you scan forward once, instead of checking every possible stretch from scratch (which for 100 elements means checking up to 5,000 different stretches). Sliding window is two pointers' sibling pattern for subarray and substring problems. Instead of pointers moving toward each other from both ends, both pointers move forward, marking out a contiguous window. Reach for it first on "longest, shortest, or best contiguous substring/subarray satisfying X" questions, which show up constantly in string-heavy interviews.

Fixed vs variable window size

There are two flavors of sliding window, and the train picture above splits neatly into both.

• Fixed-size window: the window size k is given upfront (for example, "max sum of any subarray of size k"). Slide it by adding the new right element and removing the leftmost element every step: O(1) work per step, O(n) total.
• Variable-size window: the window grows and shrinks based on a condition (for example, "longest substring with no repeating characters"). The right pointer always moves forward; the left pointer moves forward only when the window becomes invalid, catching it back up to valid.

Recognizing which flavor a problem needs is the first decision to make. If the problem states a fixed length, it is fixed-size. If it says "longest," "shortest," or "minimum" without a fixed length, it is almost always variable-size.

Remember: a fixed length in the problem means fixed-size window. "Longest" or "shortest" with no fixed length means variable-size.

Expanding and contracting the window

Picture a rubber band stretched across a row of 100 seats, covering more seats as you pull it right. The moment it covers a seat that breaks a rule, say two people with the same ticket number both under the band, you let go of the left end until the rule holds again, then keep stretching right. The variable-window template captures that exact motion, and is worth knowing cold:

The invariant that matters: the right pointer visits each index once, and the left pointer visits each index at most once, since it only moves forward. That is what makes the whole thing O(n) instead of O(n²): every index is added to the window once and removed at most once.

Harder sliding-window problems, like Minimum Window Substring below, need to track more than a simple count. The real question is whether the window currently satisfies every required character count, not just how many characters it holds. The standard trick is a have/need counter pair: need is fixed, the number of distinct characters that must be satisfied, and have increments only when a character's count in the window first reaches its required count. Comparing have == need in O(1) avoids rescanning the whole frequency map on every step.

Remember: expand right always. Contract left only while the window is invalid. have == need checks validity in O(1) instead of rescanning.

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock (LeetCode 121)

Intuition: This is a sliding window in disguise. The window is "buy day to sell day," and you want to maximize price[sell] - price[buy]. Instead of nested loops trying every pair, track the minimum price seen so far as you scan. That is an implicit left pointer that only ever moves forward when it finds a new minimum.

Approach: Walk the array once. Track min_price seen so far. At each day, compute the profit if you sold today (price - min_price) and update the best profit. Update min_price if today's price is lower.

Complexity: Time O(n), space O(1).

Common mistakes:

• Nested loops checking every buy/sell pair: O(n²), works, but interviewers expect the O(n) version.
• Updating best_profit before updating min_price on the same day. The order does not actually break this problem, since you cannot buy and sell on the same day at a profit from the exact same price, but get the order right by habit for variants.
• Confusing this with the "multiple transactions allowed" variant (LeetCode 122), which needs a different, greedy approach.

Remember: track the minimum price seen so far. The best profit at any day is today's price minus that running minimum.

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters (LeetCode 3)

Intuition: A classic variable-size window. Expand right, adding characters to a map. The moment you would add a duplicate, the window is invalid, so shrink from the left until the duplicate is gone.

Approach: Use a hash map storing the last seen index of each character, instead of a boolean set. That lets you jump the left pointer straight to just past the duplicate's previous position, instead of moving it one step at a time.

Complexity: Time O(n): each index visited once by right, and left jumps but never revisits. Space O(min(n, alphabet size)) for the map.

Common mistakes:

• Using a plain set and shrinking left one step at a time. Still O(n) amortized, but the last-seen-index version is cleaner and the standard answer.
• Forgetting the last_seen[ch] >= left check. Without it, a stale index from before the current window yanks left backward incorrectly.
• Off-by-one on window length: it is right - left + 1, not right - left.

Remember: store the last seen index of each character, and jump left straight past a duplicate instead of stepping one at a time.

Minimum Window Substring

Minimum Window Substring (LeetCode 76)

Intuition: Find the smallest window in s that contains every character of t, counting repeats. This needs the have/need tracking from earlier: expand right until the window satisfies every requirement in t, then greedily contract left as far as possible while staying valid, recording the smallest valid window found.

Approach:

1. Build a frequency map of t. need is the number of distinct characters in t.
2. Expand right across s, updating a window frequency map. When a character's window count first equals its required count, increment have.
3. While have == need (window is valid), record the window if it is the smallest so far, then contract left, decrementing have if shrinking breaks a satisfied requirement.

Complexity: Time O(|s| + |t|): building the t counter is O(|t|), and both pointers over s move forward only, giving O(|s|). Space O(|t|) for the need map, O(alphabet) for the window map.

Common mistakes:

• Recomputing "is the window valid" by scanning the whole frequency map every step, instead of tracking have/need incrementally. That turns O(n) into O(n·k).
• Off-by-one when decrementing have: it must trigger only when the count drops below the required amount, not merely when it changes.
• Not handling characters in s that are not in t at all. They should still count in window_counts (harmless) but never affect have.

The five problems in this lesson split into two families it is easy to mix up under time pressure. Buy/Sell Stock and Longest Substring are single-condition windows: one running value (min_price, last_seen) is enough to decide when to move the left pointer. Minimum Window Substring is a multi-condition window: validity depends on satisfying several counts at once, which is why it needs have/need instead of a single tracked value. Before coding, ask how many conditions define "valid" for this window. One condition, track a running value. Several conditions, reach for have/need.

Remember: one condition to satisfy, track a single running value. Several conditions at once, use have/need.

When sliding window doesn't apply

Picture the rubber band again, stretched over seats with only positive ticket numbers written on them. Adding a seat to the band only ever adds to the running total, it never subtracts, so once the total is too high, letting go of seats on the left is the only way to bring it back down: stretching further right never helps. That is the one assumption every sliding-window template leans on: once a window becomes invalid, it stays invalid until you contract it. Expanding never fixes an invalid window; only contracting does. This holds when the tracked property moves in one direction as the window grows: a sum only increases as you add non-negative numbers, a distinct-count only increases as you add elements.

It breaks the moment that stops being true. "Smallest subarray with sum at least target" works cleanly with non-negative numbers, because growing the window can only help reach the target, and shrinking can only hurt. Allow negative numbers, and adding an element can decrease the sum, so a window that looks invalid might become valid again by expanding further instead of contracting. At that point "contract while invalid" no longer proves anything.

The test to run before reaching for sliding window: can you prove that once the window is invalid, it stays invalid until contracted? If you cannot, sliding window will not crash. It will silently return a wrong answer, which is the dangerous failure mode: no exception, nothing obviously wrong to warn you.

For "subarray with sum exactly equal to k" where negatives are allowed, there is no one-directional property to exploit, so sliding window does not work. The standard tool instead is a prefix sum with a hash map of sums seen so far:

This runs in O(n) time and space, the same complexity class as sliding window, but it is a different technique: no left/right pointers, no expand/contract. It applies exactly where sliding window's one-directional requirement fails.

Before submitting a sliding-window solution, check:

• The one-directional assumption holds, or you have switched to prefix sum instead.
• Window size is right - left + 1, not right - left.
• Contract order: remove using the current left, then left += 1.
• if vs while matches whether more than one contraction step is possible: fixed-size windows contract by exactly one (if), variable-size windows can need zero to many contractions per step (while). Using if where while is needed leaves the window invalid after only one contraction, the most common sliding-window bug.
• The answer is recorded at the right point. For a longest-valid-subarray problem, record it after the contraction loop exits, once the window is valid again. For a shortest-valid-subarray problem, record it inside the contraction loop, on every contraction, since that is the smallest the window gets before it goes invalid again.
• left never moves backward anywhere in the code. That is what makes the amortized O(n) argument hold.

Remember: sliding window needs "once invalid, stays invalid until contracted." Negative numbers usually break that; reach for prefix sum + hash map instead.