Sliding Window ⏳

The sliding window is a common algorithmic technique used to efficiently process a range (window) of elements in an array or string.

Instead of recalculating values for every subarray from scratch, you reuse previous computations by moving the window step-by-step.

It is mainly used when dealing with:

• Subarrays / substrings
• Contiguous sequences
• Problems involving sum, count, maximum, minimum, or conditions over ranges

Without Sliding Window (Brute Force)

If you want to check all subarrays of size k:

• Total subarrays ≈ O(n)
• Calculating sum of each subarray takes O(k)
• Total complexity = O(n × k)

With Sliding Window

• You reuse previous sum
• Remove one element, add one element
• Total complexity = O(n)

Core Concept

Imagine a "window" of size k that moves from left to right:

[2, 1, 5, 1, 3, 2]

Window size = 3

Windows:

[2,1,5]
  [1,5,1]
    [5,1,3]
      [1,3,2]

Instead of recalculating sum every time:

new_sum = old_sum - element_leaving + element_entering

Types of Sliding Window

Fixed Size Window

Window size is constant.

• Maximum sum of subarray of size k

Problem: Find maximum sum of subarray of size k

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

Step-by-Step

1. First window sum: 2+1+5 = 8
2. Slide Window: Remove 2, add 1: 8 - 2 + 1 = 7
3. Remove 1, add 3: 7 - 1 + 3 = 9
4. Remove 5, add 2: 9 - 5 + 2 = 6

Maximum = 9

int maxSumSubarray(vector<int>& arr, int k){
    int n = arr.size();

    // Step 1: Calculate sum of first window
    int windowSum = 0;
    for(int i = 0; i < k; i++){
        windowSum += arr[i];
    }

    int maxSum = windowSum;

    // Step 2: Slide the window
    for(int i = k; i < n; i++){
        windowSum = windowSum - arr[i - k]; // remove left element
        windowSum = windowSum + arr[i];     // add new right element

        maxSum = max(maxSum, windowSum);
    }

    return maxSum;
}

Variable Size Window

Window size changes based on condition.

• Longest substring without repeating characters
• Smallest subarray with sum ≥ target

Problem: Find longest subarray with sum ≤ target

Use two pointers:

left = start of window
right = end of window

Expand right pointer
Shrink left pointer when condition breaks

int longestSubarray(vector<int>& arr, int target){
    int left = 0;
    int sum = 0;
    int maxLength = 0;

    for(int right = 0; right < arr.size(); right++){
        sum += arr[right];

        while(sum > target){
            sum -= arr[left];
            left++;
        }

        maxLength = max(maxLength, right - left + 1);
    }

    return maxLength;
}

• left is used to shrink the window from the left when the sum exceeds the target
• right is used to expand the window by iterating through the array
• sum keeps track of the current window sum
• maxLength stores the maximum valid window size found so far
• LOOP
  • sum and target used in loop condition.
  • left use twice inside loop to shrink the window.

Visualizer