Sliding Window Technique Explained With Code

The sliding window is one of those tricks that feels like magic the first time it clicks. It takes a slow solution and makes it fast with one small change in how you look at the data.

The secret is to stop throwing away work. Most slow solutions redo the same additions again and again. The window reuses them. Let me show you the waste first, then the fix.

What is the sliding window technique?

The sliding window is a method for problems that ask about a run of items sitting next to each other in a list. Things like the largest sum of any five numbers in a row, or the longest run with no repeats.

You picture a window that covers a few items at once. The window slides along the list one step at a time. As it moves, one item leaves the back and one item joins the front. You only update the small change, not the whole window.

That reuse is the whole idea. It works on an array or any list where items have a clear order. It is one of the most asked patterns in coding interviews.

The slow way, and why it wastes work

Say you want the largest sum of any 3 numbers in a row in the list [2, 1, 5, 1, 3, 2]. The obvious way is to add up each group of 3 from scratch. Add positions 1 to 3, then 2 to 4, then 3 to 5, and so on.

Here is the problem. When you slide from one group to the next, most of the numbers are the same. You add them again anyway. For a window of size k over n items, that is about n times k additions. With a big window, this gets slow fast.

The sliding window fixes this by noticing the overlap. Two groups in a row share all but one number. So why add them all again?

How does the sliding window work step by step?

Let’s find the largest sum of 3 numbers in a row in [2, 1, 5, 1, 3, 2], the fast way. Watch how the window reuses the last sum.

Start by adding the first 3 numbers, 2 plus 1 plus 5, which gives 8. That is the first window sum. Now slide one step right. The number 2 leaves and the number 1 enters. So the new sum is 8 minus 2 plus 1, which gives 7. No need to add all three again.

Slide again. The number 1 leaves and 3 enters, so the sum is 7 minus 1 plus 3, which gives 9. Slide once more. The 5 leaves and 2 enters, so the sum is 9 minus 5 plus 2, which gives 6.

The window sums were 8, 7, 9 and 6. The biggest is 9. Notice that each slide took just one subtraction and one addition, not a fresh count of three.

Sliding window code in Python and C++

The code adds the first window, then slides by subtracting the leaving item and adding the entering item. Here it is in Python.

def max_sum(arr, k):
    window = sum(arr[:k])      # sum of the first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]   # add new, drop old
        best = max(best, window)
    return best

print(max_sum([2, 1, 5, 1, 3, 2], 3))   # prints 9

The one line inside the loop is the whole trick. It adds the entering item and subtracts the leaving item in a single step. Here is the same idea in C++, the language most Indian placement tests expect.

int maxSum(int arr[], int n, int k) {
    int window = 0;
    for (int i = 0; i < k; i++) window += arr[i];
    int best = window;
    for (int i = k; i < n; i++) {
        window += arr[i] - arr[i - k];   // add new, drop old
        if (window > best) best = window;
    }
    return best;
}

Both versions build the first window once, then update it with one add and one subtract per step. That is what makes the whole scan O(n).

Two types of sliding window

There are two flavors, and knowing which one a problem needs is half the battle. The first is the fixed window, where the size never changes, like our sum of 3 example. You slide a window of set width across the list.

The second is the variable window, where the size grows and shrinks based on a rule, like the longest run with no repeated item. The window stretches while the rule holds and shrinks when it breaks. This second type pairs closely with the two pointers technique, which uses the same idea of moving boundaries.

FAQ

What is the sliding window technique?

It is a method for problems about a run of items in a row. You slide a window across the list and update only the item that leaves and the item that enters, instead of rechecking the whole window.

What is the time complexity of the sliding window?

It is O(n), because each item enters and leaves the window once. That is much faster than the O(n times k) brute force way that rechecks every window from scratch.

When should I use a sliding window?

Use it when a problem asks about items that sit next to each other, like the best sum of a fixed run or the longest run that follows a rule. The contiguous part is the clue.

What is the difference between a fixed and variable window?

A fixed window keeps the same size as it slides. A variable window grows and shrinks based on a rule, like keeping a run free of repeats. Both reuse work instead of restarting.

What is the difference between sliding window and two pointers?

They overlap a lot. A variable sliding window is really two pointers marking the window edges. Two pointers is the broader idea, and sliding window is one common use of it.

Does the sliding window only work on arrays?

It works on any ordered sequence, like an array or a string. The key is that items sit in a fixed order so a window can slide across them.

So what should you remember?

The sliding window turns a slow repeated scan into one fast pass. You slide a window across the list and update only the change, dropping the item that leaves and adding the one that enters. That reuse takes the work from O(n times k) down to O(n).

Spot it when a problem talks about a run of items in a row. Then decide if the window is fixed or variable, and you are most of the way to the answer.

Now try it. In the list [1, 4, 2, 10, 2], using the sliding window for the largest sum of 2 numbers in a row, what is that largest sum?