Sliding Window

Pronunciation: SLY-ding WIN-doh

Updated October 3, 20262 min read

In short

The sliding window technique solves problems on contiguous parts of an array or string by updating a window as it slides instead of recomputing each subarray.

What is the sliding window technique?

Take the problem of finding the largest sum of any k consecutive numbers. Summing each group separately costs O(n·k). A sliding window keeps the sum of the current k numbers; to move one step, it adds the number entering on the right and subtracts the one leaving on the left. Every element is added and removed once, so the whole scan is O(n).

Windows can be fixed or variable in size. A variable window grows by moving its right edge and shrinks by moving its left edge whenever a condition breaks. The classic example is the longest substring without repeating characters: extend the window while letters are unique, and when a repeat appears, move the left edge past the earlier copy, tracking the letters inside with a set or a map.

The same idea appears outside coding interviews: moving averages in analytics, rate limiters that count requests in the last minute, network protocols such as TCP that track a window of unacknowledged data, and streaming systems that aggregate events over time windows.

A common misconception is that sliding window works for any subarray question. It needs contiguous elements and a condition that changes predictably as the window grows or shrinks. Problems about subsequences that can skip elements, or windows over negative numbers where shrinking doesn't reliably help, usually need other techniques such as prefix sums or dynamic programming.

Key takeaways

A sliding window tracks a contiguous range and updates it step by step.
Each element enters and leaves once, so scans are O(n).
Fixed windows keep size k; variable windows grow and shrink by a condition.
Rate limiters, moving averages and TCP use the same idea.
It needs contiguous elements and a predictable condition.

Example

Fixed and variable windows (Python)python

def max_sum_of_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]     # one in on the right, one out on the left
        best = max(best, window)
    return best

def longest_unique_substring(s):
    seen, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1             # shrink past the earlier copy
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3))      # 9
print(longest_unique_substring("abcabcbb"))     # 3 ("abc")

Readers ask

What kinds of problems use a sliding window?

Problems about contiguous subarrays or substrings: maximum or minimum sums over k elements, the longest or shortest range meeting a condition, counting distinct items in ranges, and finding anagrams within a string.

What is the time complexity of a sliding window?

Usually O(n), because each element enters the window once and leaves it at most once, even though the window's size changes along the way.

How is a sliding window used in rate limiting?

A sliding window rate limiter counts requests in the most recent time span, such as the last 60 seconds, rather than in fixed calendar minutes, which avoids bursts at the boundary between two minutes.