What a sliding window is
Many array and string problems ask about a contiguous block of elements: the largest sum of 3 neighbours, the longest block that stays under a limit, the shortest block that reaches a target. The direct approach tries every block and recomputes its answer each time, which usually costs O(n²) or worse.
The sliding window technique avoids the repeated work. It keeps a window, a range of indices with a left end and a right end, together with a summary of what is inside it, such as a sum. When the window moves one step, the summary is updated by adding the element that enters and removing the element that leaves, instead of being recomputed from scratch. Each element enters the window once and leaves once, so the whole scan is O(n).
The technique is also called two pointers, because the window is described by two indices that only move forward. Most window problems come in two shapes.
Fixed-size windows
The window always holds exactly k elements. Example: the largest sum of any 3 consecutive elements of [2, 1, 5, 1, 3, 2]. The windows are [2, 1, 5], [1, 5, 1], [5, 1, 3] and [1, 3, 2], with sums 8, 7, 9 and 6, so the answer is 9.
Written the slow way, every window is summed from scratch, which costs O(n * k):
def maxSumBrute(nums: Array[Int], k: Int): Int = {
var best = Int.MinValue
for (start <- 0 to nums.length - k) {
var sum = 0
for (i <- start until start + k) sum += nums(i)
if (sum > best) best = sum
}
best
}
Sliding the window reuses the previous sum. Moving one step right adds nums(i) and drops nums(i - k):
def maxSum(nums: Array[Int], k: Int): Int = {
var sum = 0
for (i <- 0 until k) sum += nums(i)
var best = sum
for (i <- k until nums.length) {
sum += nums(i) - nums(i - k)
if (sum > best) best = sum
}
best
}
Both return 9 for the array above with k = 3. The second does one pass of constant work per element, so it is O(n). It assumes k is between 1 and nums.length.
Variable-size windows
Here the window grows and shrinks to keep a condition true. The standard pattern has a right index that moves in a for loop, and a left index that only moves inside the loop when the condition needs repairing.
Example: the length of the shortest block whose sum is at least target, for positive numbers. For [2, 3, 1, 2, 4, 3] and target = 7, the block [4, 3] has sum 7, so the answer is 2.
def shortestAtLeast(nums: Array[Int], target: Int): Int = {
var best = Int.MaxValue
var sum = 0
var left = 0
for (right <- nums.indices) {
sum += nums(right)
while (sum >= target) {
best = math.min(best, right - left + 1)
sum -= nums(left)
left += 1
}
}
if (best == Int.MaxValue) 0 else best
}
For each right, the window grows by one element. While the sum is large enough, the code records the length and then shrinks the window from the left. With [2, 3, 1, 2, 4, 3] and target = 7 it returns 2, and for [1, 1, 1] and target = 10 it returns 0, the value this version uses for "no such block".
The while inside the for does not make it quadratic. left only moves forward and never passes right, so across the whole run it moves at most n times.
Scala details for window code
- Arrays are indexed with parentheses:
nums(i). Reading past the end throwsArrayIndexOutOfBoundsException, so check bounds before indexing, as inlast < nums.length && .... - Ranges.
0 until kexcludesk,0 to nincludesn, andnums.indicesis0 until nums.length. Choosing betweentoanduntilis where off-by-one errors usually come from. - No
++. Useleft += 1. - Mutable state needs
var. The sum and the pointers change as the window moves, so they arevar. Method parameters arevals and can't be reassigned. - Built-in helpers.
nums.sliding(3)produces every window of 3 as a small array, sonums.sliding(3).map(_.sum).maxgives the same answer, 9, asmaxSum. It creates a new array for each window and sums each one again, so it costsO(n * k)and does not show the technique. Writing the window by hand is what lets you update a running sum. - Integer overflow.
Intis 32 bits and wraps silently. For large sums, useLong.
When to reach for a window
- The question is about a contiguous block, such as a subarray or substring.
- You can update the block's summary cheaply when one element enters or leaves.
- For variable windows, the condition must respond predictably to growing and shrinking. For sums, that means positive numbers: with negative numbers, removing an element can raise the sum, and the shrinking rule stops working.
Key takeaways
- A sliding window keeps a range and a running summary, and updates the summary instead of recomputing it.
- Fixed windows add one element and drop one on each step. Variable windows grow on the right and shrink on the left.
- Each index moves forward only, so the scan is
O(n)time withO(1)extra space. - In Scala, watch the range type (
untilversusto), the bounds check beforenums(i), andIntoverflow.
