Algorithms: The Sliding Window Pattern

Stop solving array problems with nested loops. Just stop. 🛑

The Problem

Given an array [1, 2, 3, 4, 5], find the maximum sum of 2 consecutive elements.

Naive Way (O(N^2)): You calculate (1+2), then (2+3), then (3+4)... using a nested loop.

Sliding Window (O(N)): Imagine a window frame of size 2.

1. Start at [1, 2]. Sum = 3.
2. Slide the window right.
3. To get the new sum, you don't need to recalculate everything. You just subtract the element leaving (1) and add the element entering (3).

def max_sum(arr, k):
    window_sum = sum(arr[:k])
    max_val = window_sum

    for i in range(len(arr) - k):
        window_sum = window_sum - arr[i] + arr[i+k]
        max_val = max(max_val, window_sum)

    return max_val

Why it matters?

In an interview, O(N^2) fits for N=1000. But for N=1,000,000 (which is real life data), O(N^2) will crash the server. O(N) will run instantly.