-
Notifications
You must be signed in to change notification settings - Fork 0
015 — Sliding Window
Two Pointers (last chapter) moved two independent indices toward each other. Sliding Window is a close cousin with a different shape: the two pointers move in the same direction, and everything between them — the "window" — is a contiguous chunk you're actively tracking the contents of. Instead of re-scanning that chunk from scratch every time it changes, you update it incrementally as the window grows or shrinks.
Picture watching a parade through a camera viewfinder that only shows a fixed-width strip of the street at a time. As the parade moves, you don't rewind and re-film the whole street to see what's currently in frame — you just let new footage enter one edge of the frame while old footage exits the other. If you're trying to answer "what's the largest crowd I can fit in frame at once," you don't need to remember every person who has ever walked past — only who's currently in the strip you're looking at, updated one person at a time as they enter or leave.
That's a sliding window: a contiguous range [left, right] over the data, where right expands the view to include new elements and left contracts it to drop old ones — and the running "state" of what's inside (a sum, a count, a set of distinct characters) is updated incrementally rather than recomputed.
Sliding Window is a strong reach when the problem statement combines a contiguity requirement with an optimization or constraint requirement:
- "Contiguous subarray/substring" paired with "longest / shortest / maximum / minimum" in the same sentence — e.g. "find the longest substring without repeating characters," "find the minimum size subarray whose sum is ≥ target." Contiguous + optimize is the single strongest signal for this pattern.
-
A fixed window size is stated explicitly — "find the maximum sum of any subarray of size
k" — this is the simplest form: the window never grows pastk, it just slides. - "No more than K distinct" or "at most K" constraints on a substring/subarray — e.g. "longest substring with at most 2 distinct characters." The window expands while the constraint holds and contracts the moment it's violated.
-
Anagram / permutation-of-a-substring problems ("find all starting indices of anagrams of
pins") — a fixed-size window sliding across, comparing character-frequency state at each step instead of re-sorting substrings.
The unifying tell: you care about a contiguous run, and re-examining that run from scratch at every position would be wasteful — the window's state can instead be updated by adding the element entering and removing the element leaving.
A variable-size window expanding with right and contracting with left, tracking the longest substring with no repeated characters in "abcabc":
string: a b c a b c
index: 0 1 2 3 4 5
right=0: window="a" [l=0,r=0] len=1 ✓ no repeats
right=1: window="ab" [l=0,r=1] len=2 ✓ no repeats
right=2: window="abc" [l=0,r=2] len=3 ✓ no repeats ← best so far
right=3: window="abca" 'a' repeats! contract:
l moves right past the OLD 'a' → l=1
window="bca" [l=1,r=3] len=3 ✓ no repeats
right=4: window="bcab" 'b' repeats! contract:
l moves past the OLD 'b' → l=2
window="cab" [l=2,r=4] len=3 ✓ no repeats
right=5: window="cabc" 'c' repeats! contract → l=3
window="abc" [l=3,r=5] len=3
┌─────────────┐
│ expand → │ right pointer always moves forward, one step per iteration
└─────────────┘
┌─────────────┐
│ ← contract │ left pointer only moves when the window violates the constraint
└─────────────┘
func slidingWindowTemplate(_ array: [Int]) -> Int {
var left = 0
var windowState = 0 // 🔧 Fill in: running sum/count/frequency-map for the window.
var best = 0 // 🔧 Fill in: whatever's being optimized (max length, min length, etc).
for right in 0..<array.count {
// 🔧 Expand: fold array[right] into the window's state.
windowState += array[right]
// 🔧 Contract: while the window violates the problem's constraint,
// shrink from the left and remove array[left] from the state.
while windowState > 0 /* placeholder condition */ {
windowState -= array[left]
left += 1
}
// 🔧 Update the answer using the CURRENT valid window [left, right].
best = max(best, right - left + 1)
}
return best
}The skeleton never changes: one forward loop over right, an expand step that folds the new element in, a while contraction loop that shrinks left until the window is valid again, and an answer update using the current window bounds. Fixed-size windows are a simplification of this same shape — contract exactly when right - left + 1 > k, instead of contracting based on a data-driven constraint.
Longest Substring Without Repeating Characters — given a string s, find the length of the longest substring with no repeated characters.
func lengthOfLongestSubstring(_ s: String) -> Int {
let chars = Array(s)
var left = 0
var lastSeenIndex: [Character: Int] = [:] // window state: last index each char appeared at
var best = 0
for right in 0..<chars.count {
let c = chars[right]
// Contract: if c was last seen INSIDE the current window, jump left
// past that previous occurrence — no need to step one at a time.
if let seenAt = lastSeenIndex[c], seenAt >= left {
left = seenAt + 1
}
lastSeenIndex[c] = right
best = max(best, right - left + 1)
}
return best
}
// smoke test
print(lengthOfLongestSubstring("abcabc")) // 3
print(lengthOfLongestSubstring("bbbbb")) // 1
print(lengthOfLongestSubstring("pwwkew")) // 3Mapped onto the template: windowState is the lastSeenIndex dictionary instead of a running number — the "expand" step records where c was just seen, and the "contract" step is a single conditional jump instead of a while loop, because a dictionary lookup tells us exactly how far left needs to move in one shot rather than one element at a time. best is updated identically to the template, using the current [left, right] window width.
A sliding window is a camera viewfinder tracking a parade — new footage enters one edge, old footage exits the other, and you never rewind to re-film what's already left the frame.
A problem asks: "Given an array of positive integers and a target sum, find the length of the shortest contiguous subarray whose sum is ≥ target." Would you expand-and-contract the window the same way as the "longest substring" example above, or would the direction of the contraction logic flip? Walk through what triggers a contraction here versus what triggered it in the worked example.