Om's Brain

2. Sliding Window

2 min read

1️⃣ Fixed Size Sliding Window Template

📌 Use when window size is constant (k)

Pattern template

  • Build first window
  • Slide by:
    • add new element
    • remove old element
    • update answer
// Step 1: Build first window of size k
for (int i = 0; i < k; i++) {
	add(arr[i]);
}
 
// Use first window
update_answer();
 
// Step 2: Slide window
for (int i = k; i < n; i++) {
 
	// Add new element
	add(arr[i]);
 
	// Remove old element
	remove(arr[i - k]);
 
	// Update answer
	update_answer();
}

Example: max sum of subarray of size k

int maxSubarraySum(vector<int>& arr, int k) {
    int n = arr.size();
 
    // Edge case: window size larger than array
    if (k > n) return -1;
 
    int windowSum = 0;
 
    // Step 1: Build first window of size k
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
 
    // Initialize result using first window
    int maxResult = windowSum;
 
    // Step 2: Slide window
    for (int i = k; i < n; i++) {
        // add new element to window
        windowSum += arr[i];
 
        // remove old element
        windowSum -= arr[i - k];
 
        // Update answer
        maxResult = max(maxResult, windowSum);
    }
 
    return maxResult;
}
 
// TC - `O(n)` 
// SC - `O(1)`

2️⃣ Variable Size Sliding Window Template

📌 Use when window size is not fixed
You expand and shrink based on a condition.

Pattern

  • Expand window using right
  • Add the new element in Window
  • Keep checking condition
    • while invalid:
      • shrink from left to till it becomes valid
  • update answer
  • Repeat
int left = 0;
 
for (int right = 0; right < n; right++) {
 
    // 1. Add new element in window
    add(arr[right]);
 
    // 2. Shrink from left while invalid
    while (invalid_window()) {
        remove(arr[left]);
        left++;
    }
 
    // 3. Use valid window
    update_answer();
}

Example: Longest Substring Without Repeating Characters 

int lengthOfLongestSubstring(string s) {  
	int left = 0, maxLen = 0;  
	unordered_map<char, int> freq;  
 
	// Step 1: Expand window  
	for (int right = 0; right < s.size(); right++) {  
		char c = s[right];  
		freq[c]++;  
 
		// Step 2: Shrink while invalid  
		while (freq[c] > 1) {  
			freq[s[left]]--;  
			left++;  
		}  
 
		// Step 3: Update answer  
		maxLen = max(maxLen, right - left + 1);  
	}  
 
	return maxLen;  
}  
 
// TC - `O(n)`  
// SC - `O(k)` // k = unique chars

1 item under this folder.