Sliding Window Technique in Data Structures

What is the Sliding Window Technique?

The Sliding Window is one of the most powerful and widely-used algorithmic patterns in competitive programming and coding interviews. It is used to perform operations on a contiguous sequence of elements (subarrays or substrings) within a linear data structure (arrays or strings).

The core idea is elegantly simple: instead of recomputing the result for every subarray from scratch — which costs O(K × N) or O(N²) time — you maintain a "window" that slides across the array. As the window moves:

• You add the new element entering from the right side
• You remove the element leaving from the left side

This keeps computations at O(N) linear time regardless of window size.

Array: [2, 1, 5, 1, 3, 2]   Find max sum subarray of size K=3

Window 1: [2, 1, 5], 1, 3, 2  → Sum = 8
Slide:      2, [1, 5, 1], 3, 2  → Sum = 8 - 2 + 1 = 7
Slide:      2, 1, [5, 1, 3], 2  → Sum = 7 - 1 + 3 = 9   ← Maximum
Slide:      2, 1, 5, [1, 3, 2]  → Sum = 9 - 5 + 2 = 6

Notice how each new window's sum is computed in O(1) by adjusting the previous result — no inner loop needed!

When to Use the Sliding Window

Look for these signals in a problem:

• Keywords: subarray, substring, contiguous, window, consecutive
• Asking for maximum/minimum sum, longest/shortest subarray satisfying a condition
• The data is in an array or string (linear structure)
• Brute force would involve nested loops

Fixed Window vs. Variable Window

1. Fixed Window Size

The size of the window K is constant — it never changes as it slides from left to right.

Pattern:

• Initialize the window with the first K elements
• Compute the initial result
• Slide: remove arr[left], add arr[right], update result
• Track best result across all windows

Example: Maximum Sum of K Consecutive Elements

JavaScript:

javascript
function maxSumSubarray(arr, k) {
    let windowSum = 0;
    let maxSum = 0;

    // Build initial window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];  // Add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // Output: 9

Python:

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

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # Slide window
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # Output: 9

C++:

cpp
int maxSumSubarray(vector<int>& arr, int k) {
    int windowSum = 0, maxSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];
    maxSum = windowSum;
    for (int i = k; i < arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

2. Variable Window Size

The window size expands and contracts dynamically based on a constraint condition. This is more powerful and handles a wider class of problems.

Pattern:

• Use two pointers: left = 0, right = 0
• Expand window: move right forward, adding arr[right] to the window
• If constraint is violated: shrink window by moving left forward (removing arr[left]) until constraint is satisfied again
• Track best window size at every valid state

Example: Longest Substring Without Repeating Characters

javascript
function lengthOfLongestSubstring(s) {
    const seen = new Map();  // char → most recent index
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];

        // If we've seen this character inside the window, shrink from left
        if (seen.has(char) && seen.get(char) >= left) {
            left = seen.get(char) + 1;
        }

        seen.set(char, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // Output: 3 ("abc")
console.log(lengthOfLongestSubstring("pwwkew"));   // Output: 3 ("wke")

Trace for "abcabcbb":

right=0: window="a", maxLen=1
right=1: window="ab", maxLen=2
right=2: window="abc", maxLen=3
right=3: 'a' seen at 0, move left=1, window="bca", maxLen=3
right=4: 'b' seen at 1, move left=2, window="cab", maxLen=3
right=5: 'c' seen at 2, move left=3, window="abc", maxLen=3
right=6: 'b' seen at 4, move left=5, window="cb", maxLen=3
right=7: 'b' seen at 6, move left=7, window="b", maxLen=3

Advanced Example: Minimum Window Substring

Find the smallest substring of s that contains all characters of pattern t.

javascript
function minWindow(s, t) {
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }

    let left = 0, formed = 0, required = need.size;
    let minLen = Infinity, minLeft = 0;
    const window = new Map();

    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        window.set(char, (window.get(char) || 0) + 1);

        if (need.has(char) && window.get(char) === need.get(char)) {
            formed++;  // This character's frequency requirement is met
        }

        // Try to shrink window while all requirements are met
        while (formed === required) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }

            const leftChar = s[left];
            window.set(leftChar, window.get(leftChar) - 1);
            if (need.has(leftChar) && window.get(leftChar) < need.get(leftChar)) {
                formed--;  // Requirement no longer satisfied after shrink
            }
            left++;
        }
    }

    return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}

console.log(minWindow("ADOBECODEBANC", "ABC")); // Output: "BANC"

Example: Subarray with Sum Equal to K

Count the number of subarrays that sum exactly to K (using HashMap technique):

javascript
function subarraySum(nums, k) {
    const prefixCount = new Map([[0, 1]]);
    let count = 0, prefixSum = 0;

    for (const num of nums) {
        prefixSum += num;
        // If (prefixSum - k) was seen before, a valid subarray exists
        count += prefixCount.get(prefixSum - k) || 0;
        prefixCount.set(prefixSum, (prefixCount.get(prefixSum) || 0) + 1);
    }

    return count;
}

console.log(subarraySum([1, 1, 1], 2));     // Output: 2
console.log(subarraySum([1, 2, 3], 3));     // Output: 2

Example: Maximum of All Subarrays of Size K (Deque)

For each sliding window of size K, find the maximum element in O(N) using a monotonic deque:

javascript
function maxSlidingWindow(nums, k) {
    const deque = [];   // Stores indices, decreasing by value
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        // Remove elements out of the window
        while (deque.length > 0 && deque[0] < i - k + 1) {
            deque.shift();
        }
        // Remove smaller elements from the back (they'll never be max)
        while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop();
        }
        deque.push(i);

        // Window has reached full size — record maximum
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// Output: [3, 3, 5, 5, 6, 7]

Advantages and Disadvantages

Complexity Reference

Real World Usages

• TCP Congestion Control & Flow Control: The TCP sliding window protocol manages how many packets can be in transit before receiving acknowledgement, preventing network overload.
• Data Streaming & Analytics: Computing rolling averages of stock prices, CPU usage, or network logs over the last N seconds/minutes.
• Video Processing & Computer Vision: Convolution filters and edge detection algorithms slide a kernel (fixed window) across pixel matrices.
• Text Processing: Plagiarism detection tools slide a fixed-size "shingle" across documents to compare text similarity.
• Database Queries: Window functions in SQL (OVER, PARTITION BY) compute rolling aggregates across data rows.

Common Interview Patterns

1. Maximum/Minimum Sum Subarray of Size K: Fixed window, O(N) solution.
2. Longest Substring Without Repeating Characters: Variable window with HashMap.
3. Minimum Window Substring: Variable window matching character frequency requirements.
4. Subarray Product Less Than K: Variable window maintaining running product.
5. Maximum of All Subarrays of Size K: Fixed window with monotonic deque.
6. Fruit Into Baskets: Variable window with at most 2 distinct values.
7. Find All Anagrams in a String: Fixed window with character frequency matching.

Frequently Asked Questions

Q: How do I recognize a sliding window problem?
A: Look for these patterns: (1) The problem asks about contiguous subarrays or substrings, (2) You need a maximum/minimum/count of something over a range, (3) Brute force requires nested loops (O(N²)). If all three apply, sliding window likely reduces it to O(N).

Q: What is the difference between fixed and variable sliding windows?
A: A fixed window has a predetermined constant size K — it simply slides across without resizing. A variable window expands and contracts dynamically based on whether the current window satisfies a constraint, using two pointers that move independently.

Q: Why do we use a deque (double-ended queue) in the maximum sliding window problem?
A: The deque maintains a monotonically decreasing sequence of indices. When a new element arrives that is larger than elements already in the deque, those smaller elements are removed because they can never be the maximum of any future window. This ensures the front of the deque always holds the index of the current window's maximum, achieving O(1) max lookup per window.

Q: Can sliding window work on 2D matrices?
A: Yes! For 2D sliding window problems, you fix one dimension (e.g., slide row-by-row) and apply a 1D sliding window horizontally. This is used in image processing convolutions and 2D sum queries.

Q: When does sliding window NOT work?
A: Sliding window fails when the problem requires non-contiguous elements (like subsequences), when the array contains negative numbers and you need to find a subarray summing to K (use prefix sum + HashMap instead), or when the "window" condition is non-monotonic (shrinking the window doesn't necessarily fix a violation).