What Is the Sliding Window Technique?

The sliding window technique fits problems where you want the best answer over a contiguous range of an array or string, and where you can maintain a running summary of that range as it moves. The two ingredients are a window, which is a range of the input, and an efficient way to update the summary when the window shifts by one position on either side.

A good fit usually has three properties. There is a natural window size, either fixed as in a maximum sum of k consecutive elements or variable as in the longest substring without repeated characters. Adding a character to the window and removing one from it can both be done in constant time, usually through a counter or a running sum. And the answer can be read off the window summary at each step without recomputing anything.

The technique exists to avoid the nested loop. A brute force approach tries every starting position and scans forward, which is quadratic. The sliding window reuses the work done for the previous window: when the window moves one step, one element leaves and one arrives, and you update the summary accordingly rather than starting over.

The trade-off to name is that the window technique needs an invertible or incremental summary. If removing an element from the window requires rescanning the window, the technique buys nothing. A running sum works because subtraction undoes addition. A maximum does not work in the same way, because you cannot un-set the maximum, which is why the maximum sliding window problem needs a monotonic deque instead. Recognising which of the two you are dealing with is the real skill here, and it is a question interviewers ask precisely to see whether you understand the constraint rather than memorising a template.

Compute the sum of the first window, then slide the window one position at a time. At each slide, subtract the value leaving the window and add the value entering it, and keep the largest sum seen. The whole thing is a single pass with constant extra space.

def max_fixed_window(nums, k):
    if k <= 0 or k > len(nums):
        return 0
    total = sum(nums[:k])
    best = total
    for i in range(k, len(nums)):
        total += nums[i] - nums[i - k]
        best = max(best, total)
    return best

print(max_fixed_window([2, 1, 5, 1, 3, 2], 3))
print(max_fixed_window([1, 2, 3], 4))

The outputs are 9 and 0. For the first array the three windows sum to 8, 7, 9 and 6, and the best is 9. The second call asks for a window larger than the array, so the guard returns 0 rather than trying to read past the end.

The mechanism is the incremental update. The value leaving the window is at index i minus k and the value entering is at index i, so one addition and one subtraction replace a fresh sum of k elements. That is the whole difference between linear and quadratic: summing every window from scratch would cost k times n, while the sliding version costs n.

The trade-off to state is that this works because addition can be undone by subtraction. The same trick does not help when the summary is a maximum, a median, or a product that can overflow, and for those you need a different structure, such as a monotonic deque for a maximum or a running median structure for a median. It is also worth noting that the initial sum of the first window is computed with a slice, which is O of k, so the total cost is O of n plus O of k rather than exactly O of n. That detail is small, but naming it shows you have thought about the constant factors.