Sliding Window - Introduction

Consider having an array or string and being asked a question about a contiguous subarray or substring, for example, the maximum sum of any k consecutive elements. A brute-force approach would use two nested loops and run in O(n·k) time.

The Sliding Window technique eliminates this redundant work by maintaining a window defined by two pointers, left and right: and sliding this window across the array, updating the result incrementally rather than recomputing it from scratch each time.

There are two main variants:

• Fixed-size window: the window size k is constant. Both pointers move together.
• Dynamic (variable) window: the window size changes based on a condition. The right pointer expands the window; the left pointer shrinks it when the condition is violated.

In a fixed-size window, the window always contains exactly k elements. As the window slides right by one position, the rightmost element enters and the leftmost element leaves.

Sliding Window O(n) approach:

public int maxSumFixedWindow(int[] nums, int k) {
    int windowSum = 0;

    // Compute sum of first window
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    int maxSum = windowSum;

    // Slide the window: add right element, remove left element
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Complexity:

• Time: O(n). Single pass through the array.
• Space: O(1). No extra space needed.

In a dynamic window, the window expands by moving right forward and shrinks by moving left forward whenever a constraint is violated. This is the more common variant used in string/substring problems.

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, windowSum = 0;
    int minLen = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        windowSum += nums[right]; // expand window

        // Shrink window from left while condition is satisfied
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

General template for dynamic sliding window:

int left = 0;
// some window state (e.g. sum, frequency map)

for (int right = 0; right < n; right++) {
    // 1. Add element at right to the window state

    // 2. Shrink window from left if constraint is violated
    while (/* window is invalid */) {
        // Remove element at left from window state
        left++;
    }

    // 3. Update answer with current valid window [left, right]
}

Sliding window is a strong fit when the problem asks about:

• Maximum or minimum of a contiguous subarray or substring of fixed or variable length.
• Longest or shortest substring satisfying a condition (e.g. at most k distinct chars).
• Counting subarrays that meet a criterion (e.g. sum equals k).
• Problems involving contiguous elements, not arbitrary subsets.

• Time complexity: O(n). Each element is added to the window once and removed at most once, so the total number of operations is O(2n) = O(n).
• Space complexity: O(1) to O(k). O(1) for simple sum-based windows; O(k) when using a frequency map (e.g. for character-count windows).