Sliding Window

🧠 Concept

The Sliding Window technique involves maintaining a window (subset of elements) that slides over the data structure to find a solution. It converts $O(N^2)$ brute force solutions into $O(N)$ linear time solutions.

🖼️ Visualizing the Window

Refers to a sub-array or substring that “slides” from left to right.

Input: [ 2, 1, 5, 1, 3, 2 ], k=3

Window 1: [ 2, 1, 5 ] -> Sum = 8
           ^     ^

Window 2:    [ 1, 5, 1 ] -> Sum = 7
              ^     ^

Window 3:       [ 5, 1, 3 ] -> Sum = 9
                 ^     ^

🛠️ Types of Sliding Window

There are two primary types of sliding windows:

1. Fixed Size Window

The size of the window ($k$) is fixed. We need to process every subarray of size $k$.

Use Case: Find max sum of subarray of size $k$, First negative number in every window of size $k$.
Mechanism:
1. Initialize window for first $k$ elements.
2. Slide one step: Remove outgoing element, Add incoming element.

2. Variable Size Window

The window size changes based on certain conditions. We expand the window until the condition is broken, then shrink it.

Use Case: Longest substring without repeating characters, Smallest subarray with sum $\ge S$.
Mechanism:
1. Expand right pointer to include elements.
2. While condition is invalid, shrink left pointer.
3. Update result.

📝 Code Templates

🔒 Fixed Size Template (Java)

public int fixedSlidingWindow(int[] arr, int k) {
    int currentSum = 0;
    int maxSum = Integer.MIN_VALUE;

    // 1. Initialize first window
    for (int i = 0; i < k; i++) {
        currentSum += arr[i];
    }
    maxSum = currentSum;

    // 2. Slide the window
    for (int i = k; i < arr.length; i++) {
        currentSum += arr[i];       // Add new element
        currentSum -= arr[i - k];   // Remove old element
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

🔓 Variable Size Template (Java)

This is the most versatile template that solves 90% of sliding window problems.

public int variableSlidingWindow(int[] arr) {
    int start = 0, end = 0;
    int invalidCount = 0; // or Map/Set to track state
    int maxLen = 0;

    while (end < arr.length) {
        // 1. Add element at 'end' to current state
        // update(arr[end]);

        // 2. While condition is broken, shrink window from 'start'
        while (/* condition is invalid */) {
            // remove(arr[start]);
            start++;
        }

        // 3. Update answer (window is valid here)
        maxLen = Math.max(maxLen, end - start + 1);

        end++; // Expand window
    }

    return maxLen;
}

🚀 Classic Problems

1. Max Sum Subarray of Size K

Problem: Given an array of integers and a number $k$, find the maximum sum of a subarray of size $k$.

View Solution

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

    for (int i = 0; i < nums.length; i++) {
        windowSum += nums[i];

        if (i >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= nums[i - (k - 1)];
        }
    }
    return maxSum;
}

2. Longest Substring Without Repeating Characters

Problem: Given a string, find the length of the longest substring without repeating characters.

View Solution

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, right = 0;
    int maxLen = 0;

    while (right < s.length()) {
        if (!set.contains(s.charAt(right))) {
            set.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
            right++;
        } else {
            set.remove(s.charAt(left));
            left++;
        }
    }
    return maxLen;
}

3. Minimum Size Subarray Sum

Problem: Given an array of positive integers and a target value, find the minimal length of a contiguous subarray of which the sum is $\ge$ target.

View Solution

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

    for (int end = 0; end < nums.length; end++) {
        sum += nums[end];

        while (sum >= target) {
            minLen = Math.min(minLen, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }

    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

🎯 Cheat Sheet

Type	Identifiers	Complexity
Fixed	”Subarray of size k”, “Sum of every k elements”	Time: $O(N)$ Space: $O(1)$
Variable	”Longest substring”, “Smallest subarray”, “Max consecutive ones”	Time: $O(N)$ Space: $O(1)$ or $O(K)$