What a sliding window is
Many array problems ask about a contiguous stretch of elements: the largest sum of 3 neighbours, the longest run with a bounded sum, the shortest run that contains something. The obvious solution examines every stretch separately and adds its elements up again. That repeats a lot of work, because two neighbouring stretches share almost all their elements.
A sliding window keeps one stretch, the window, and moves it along the array. When the window moves one step, only the element that enters and the element that leaves change. The window's sum (or count, or whatever it tracks) is updated by those two elements instead of being recomputed. In Swift terms, the window is a pair of indices into the array and a running value, not a new array.
Usually the technique is described with two indices, often called left and right (or first and last), that both only move forward. Because neither goes backward, every element is added once and removed once, and the whole scan costs O(n) even when two loops are nested.
A fixed-size window
The simplest case has a window of a fixed size k. Take the problem: find the largest sum of k consecutive elements.
The slow way recomputes every sum from scratch, O(n * k) in total:
func maxSumNaive(_ nums: [Int], _ k: Int) -> Int {
var best = Int.min
for start in 0...(nums.count - k) {
var sum = 0
for i in start..<(start + k) { sum += nums[i] }
best = max(best, sum)
}
return best
}
The window version computes the first sum once, then slides: add the element that enters on the right and subtract the one that leaves on the left.
func maxSumWindow(_ nums: [Int], _ k: Int) -> Int {
var sum = 0
for i in 0..<k { sum += nums[i] }
var best = sum
for i in k..<nums.count {
sum += nums[i] - nums[i - k]
best = max(best, sum)
}
return best
}
For nums = [2, 1, 5, 1, 3, 2] and k = 3, both functions return 9, the sum of 5, 1, 3. The window version does about n additions instead of n * k, so its time is O(n).
A variable-size window
In many problems the window size is the answer, so it grows and shrinks. The usual pattern is: move right forward to add one element, then, while the window breaks the rule, move left forward to drop elements. After the shrinking, the window is valid again, and the code records the result.
Take the problem: for positive integers, find the length of the longest contiguous run with a sum of at most s.
func longestAtMost(_ nums: [Int], _ s: Int) -> Int {
var left = 0, sum = 0, best = 0
for right in 0..<nums.count {
sum += nums[right]
while sum > s {
sum -= nums[left]
left += 1
}
best = max(best, right - left + 1)
}
return best
}
With [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and s = 11 it returns 6. With [5, 6] and s = 4 it returns 0, because even the smallest window, after shrinking, is empty.
Each element enters the window once, when right reaches it, and leaves at most once, when left passes it. The inner while loop looks like it could make the code quadratic, but left never moves back, so all the inner iterations together make at most n steps. The total is O(n).
The rule that lets the window shrink from the left is a property of the problem. Here all numbers are positive, so dropping an element always lowers the sum. If the array could contain negative numbers, dropping an element could raise the sum, and this simple scan would not be correct.
Swift details that matter
- Ranges and indices.
0..<nexcludesnand0...nincludes it. A range whose upper bound is below its lower bound, such ask..<nums.countwhenkis larger than the array, stops the program with an error. Check thatkfits in the array before using such a range. - Arrays are bounds-checked. Reading
nums[i]with an index outside the array also stops the program. In a loop condition such asright < nums.count && ..., put the bounds check first, because&&skips the right-hand side when the left one is false. - No
++. Swift has no increment operator, so the loops writeleft += 1. - Overflow stops the program.
Intis 64 bits, and an addition that overflows it crashes instead of wrapping. Window sums of normal-sized inputs are far from that limit. - Index, don't copy. A window can be written as a slice such as
nums[left...right], but summing a slice each time brings back the repeated work. Keep a running value and two indices.
Recognising the pattern
A sliding window is worth trying when:
- the answer concerns a contiguous subarray or substring;
- there is a quantity that can be updated when one element enters or leaves, such as a sum or a count;
- growing the window pushes the quantity one way and shrinking pushes it the other, so you know which end to move.
The fixed-size form fits questions that name the size, like "the best sum of k neighbours". The variable-size form fits questions about the longest or shortest stretch that satisfies a condition.
Where it appears in this chapter
The lessons that follow apply the same two ideas. Problems such as the maximum sum of a subarray of a given length use a fixed window. Problems such as the longest subarray whose sum stays at most S use a variable window, where one index grows the window and the other drops elements from the front. In each of them, the steps are the same: decide what the window tracks, say what makes it valid, and move the two ends so that neither goes backward.
Key takeaways
- A sliding window is a range of the array described by two indices and a running value, updated as the range moves.
- A fixed-size window adds the entering element and subtracts the leaving one, turning
O(n * k)intoO(n). - A variable-size window grows with
rightand shrinks withleftwhile the rule is broken. - Both ends only move forward, so every element is handled a constant number of times and the scan is
O(n). - In Swift, mind range bounds, array indices and the lack of
++, and write the bounds check first in a combined loop condition.
