When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
Predict first
What do the longest-unique and best-sum windows print?
func longestUnique(_ s: String) -> Int {
let c = Array(s)
var last: [Character: Int] = [:]
var left = 0, best = 0
for (right, ch) in c.enumerated() {
if let p = last[ch], p >= left { left = p + 1 } // shrink past the earlier copy
last[ch] = right
best = max(best, right - left + 1)
}
return best
}
func bestSum(_ a: [Int], window k: Int) -> Int? {
guard k > 0, a.count >= k else { return nil }
var sum = a[0..<k].reduce(0, +), best = sum
for i in k..<a.count { sum += a[i] - a[i - k]; best = max(best, sum) } // slide: add one, drop one
return best
}
for s in ["abcabcbb", "bbbbb", "pwwkew", ""] { print("longest unique run in \"\(s)\":", longestUnique(s)) }
print("best sum of 3:", bestSum([2, 1, 5, 1, 3, 2], window: 3) ?? -1)
print("best sum of 9:", bestSum([2, 1], window: 9) ?? -1)- 3 / 1 / 3 / 0 then 9 / -1
- 3 / 1 / 4 / 0 then 9 / -1
- 3 / 5 / 3 / 0 then 6 / -1
Mental model. A magnifying glass sliding along a line of text: you never re-read the whole line, you just notice the letter that entered on the right and the one that left on the left.
Use a sliding window when the question is about a contiguous run of an array or string (a subarray or substring) and you can update an answer for the run in O(1) when it gains one element on the right or loses one on the left. Brute force re-scans every run from scratch, O(n²) or worse; the window carries the state forward, O(n). Fixed size (best sum of k items): add the new element, drop the one that left, compare, as bestSum shows (9 for [2,1,5,1,3,2] with k = 3). Variable size (longest run without a repeat): grow the right edge each step and move the left edge just far enough to restore the rule; in longestUnique, a dictionary of last positions lets the left edge jump straight past the earlier copy.
The recognisable clues are “longest/shortest/maximum substring or subarray such that…” and a rule that can be checked incrementally (a count, a sum, a set of distinct characters). It does not fit when the rule breaks monotonic movement (negative numbers in a “sum at least k” problem usually need prefix sums) or when elements may be skipped (that is a subsequence problem, usually dynamic programming). Guard the inputs: k larger than the array, k = 0, and the empty string, all shown in the check. Reported at Google (anonymous, unverified).
Repeats shrink the window from the left, an empty string gives 0, and a window larger than the array is reported as -1 here.
Common traps
- Moving the left edge backwards or not at all, so the window stops being valid.
- Using a window for non-contiguous picks. Skipping elements makes it a different problem.
They might follow up with
- What about “shortest subarray with sum at least k” and negatives? A deque over prefix sums; the plain window does not work.
- How do you track “at most k distinct characters”? A dictionary of counts; shrink from the left while it has more than k keys.
Related questions
- 29.1.1 Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get…
- 29.2.9 Find the longest run in a float array where adjacent chosen values differ by at most 1. Why must you ask…
- 29.1.7 Next permutation: rearrange an array into the next lexicographically greater order, in place. Walk through…
← Next permutation: rearrange an array into the next lexicographically…