What a sliding window is
Many array problems ask about a contiguous stretch of elements: the largest sum of 3 neighbours, the longest stretch whose sum stays under a limit, the shortest stretch that contains something. The obvious solution tries every stretch, which means two nested loops and O(n²) time, or worse when each stretch also has to be summed.
The sliding window technique avoids this. It keeps one window, described by two indices, and moves it along the array. When the window moves, you don't recompute everything. You update what changed: the element that enters at one end and the element that leaves at the other. Each index enters the window once and leaves at most once, so the whole scan is O(n). The technique is also called two pointers, because the window is the space between a left index and a right index that both move forward.
A window in Kotlin
A window needs no special data structure. It is a pair of indices, such as left and right, plus the facts about the window you want to keep current, such as its sum. For an IntArray called nums, the window covers nums[left..right], and its length is right - left + 1.
The kinds of problems fall into two groups.
Fixed-size window
The window always has length k. Build the first window, then slide it one step at a time: add the new element on the right, remove the one that falls off on the left.
fun maxSumOfK(nums: IntArray, k: Int): Int {
var sum = 0
for (i in 0 until k) sum += nums[i]
var best = sum
for (i in k until nums.size) {
sum += nums[i] - nums[i - k]
best = maxOf(best, sum)
}
return best
}
For nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and k = 3, maxSumOfK returns 10, from the window 3, 2, 5. Every step costs one addition and one subtraction, so the whole call is O(n), compared with O(n * k) if each window were summed again.
Variable-size window
The window grows and shrinks to satisfy a condition. A common pattern: the right end advances through the array one element at a time, and the left end advances only when the window breaks the rule, until the window is valid again.
fun longestAtMost(nums: IntArray, s: Int): Int {
var left = 0
var sum = 0
var best = 0
for (right in nums.indices) {
sum += nums[right]
while (sum > s) {
sum -= nums[left]
left++
}
best = maxOf(best, right - left + 1)
}
return best
}
This returns the length of the longest stretch of positive numbers with a sum of at most s. With the same array and s = 11, it returns 6. A brute force that tries every start and end gives the same answer, but it is quadratic. In the window version, the inner while loop does not make the code quadratic: left only moves forward, so across the whole function it moves at most n times.
When it applies
The technique works when you can update the window's state cheaply as elements enter and leave. That usually means the window's property behaves predictably:
- With positive numbers and a sum limit, adding an element can only raise the sum and removing one can only lower it, so a window that is too large can always be fixed by shrinking from the left.
- With counts of values, such as the number of distinct values, a map from each value to its count can be updated in constant time, and the number of keys is the answer.
- With negative numbers and a sum condition, shrinking a window can make the sum larger, so the simple shrink-and-grow logic stops being valid. Other tools are needed.
Common mistakes in Kotlin
- Reading past the end. Kotlin arrays are bounds-checked. An index outside the array throws an
ArrayIndexOutOfBoundsException. For example, callingmaxSumOfK(intArrayOf(1, 2), 3)stops with "Index 2 out of bounds for length 2", because the first window needs three elements. Guard the case wherekis larger than the array. - Checking the bound too late. In a condition such as
right < nums.size && sum + nums[right] <= s, put the index check first. The&&operator skips the right side when the left side is false. - Off-by-one in the length. A window from
lefttorightinclusive hasright - left + 1elements. If the right index is exclusive, the length isright - left. Pick one convention and keep it. - Forgetting to remove the leaving element. If the state isn't updated when
leftmoves, the window's sum or counts describe elements that are no longer inside it. - Recomputing instead of updating. Summing the window again inside the loop turns an
O(n)scan back intoO(n * k). - Int overflow. Kotlin's
Intis 32 bits and wraps silently. If the numbers are large, keep the running sum in aLong.
How you will use it
The lessons in this chapter use the technique in three ways. One problem asks for the longest subarray whose sum is at most a limit, which is the variable window above. Another asks for the longest subarray with at most K distinct integers, where a HashMap<Int, Int> counts the values in the window. The pattern is always the same: decide what the window must satisfy, decide what state describes it, and move the two indices so that each moves forward only.
Key takeaways
- A window is two indices and some state. In Kotlin, no special type is needed.
- Fixed windows slide in lockstep. Variable windows grow on the right and shrink on the left.
- Update the state as elements enter and leave. Never recompute it from scratch.
- Each index moves forward only, so the scan is
O(n)even with a nestedwhile. - Check array bounds before reading, and use
Longfor large sums.