Premium

Sliding Window

Basic Algorithms
≈ 2 min read

When a contiguous range matters

A sliding window is used when a problem works with consecutive elements of an array: for example, when we need to find the best subarray of a fixed length. Instead of recalculating the result for every range from scratch, we can update the known value when the window shifts by one position.

Suppose we need to find the maximum sum of any three neighboring elements. First, we calculate the sum of the first window. 

int windowSize = 3;
int windowSum = 0;

for (int i = 0; i < windowSize; i++) {
    windowSum += numbers[i];
}

int maxSum = windowSum;

Shift instead of recalculating

When moving to the next window, almost all elements remain the same. We only need to subtract the element that left on the left and add the new element that entered on the right. 

for (int right = windowSize; right < numbers.length; right++) {
    int left = right - windowSize;

    windowSum -= numbers[left];
    windowSum += numbers[right];
    maxSum = Math.max(maxSum, windowSum);
}

After the initial calculation, each shift requires a constant number of operations. Therefore, the whole algorithm runs in O(n) time, whereas fully recalculating every window sum would repeat unnecessary work.

What the window can maintain

A window can maintain more than just a sum. Depending on the problem, it can track the number of suitable elements, a current constraint, or another piece of state that can be updated when the boundaries change. The key question is always the same: can we move from one neighboring range to the next without computing everything again.

A sliding window works with a contiguous range. If the selected elements may be located at arbitrary positions in the array, that is a different problem model, and the window technique may not fit.
Back Next