Sliding Window Technique
Definition
The Sliding Window technique is used to perform operations on a specific “window” size of an array or string. Instead of recalculating the entire window every time, you “slide” it by one position: add the new element entering the window and remove the old element leaving it. 
How it Works
- Create Window: Start with the first K elements.
- Slide: To move to the next position, subtract the element that just fell out of the left side and add the element entering the right side.
- Benefit: This avoids nested loops.
Real-World Analogy
Train Windows: Imagine a long train passing by. You have a window frame that allows you to see exactly 3 train cars at a time. As the train moves, you don’t look at a completely new set of cars; you just see one new car appear on the right, and one old car disappear on the left.
Example
Problem: Find the maximum sum of any contiguous subarray of size $k=3$. Array: [2, 1, 5, 1, 3, 2]
- Window 1: [2, 1, 5] Sum = 8.
- Slide: Remove 2, Add 1. New Window [1, 5, 1] Sum = 7.
- Slide: Remove 1, Add 3. New Window [5, 1, 3] Sum = 9. (Max)
Code Example
PythonJavaCC++
# Maximum Sum Subarray of size k (Sliding Window)
def max_sum_subarray(arr, k):
# Sum of first window
max_sum = current_sum = sum(arr[:k])
# Slide the window
for i in range(len(arr) - k):
current_sum = current_sum - arr[i] + arr[i+k]
max_sum = max(max_sum, current_sum)
return max_sum
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9
public class SlidingWindow {
static int maxSumSubarray(int arr[], int k) {
int currentSum = 0;
// First window
for (int i = 0; i < k; i++)
currentSum += arr[i];
int maxSum = currentSum;
// Slide window
for (int i = 0; i < arr.length - k; i++) {
currentSum = currentSum - arr[i] + arr[i+k];
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int arr[] = {2,1,5,1,3,2};
System.out.println(maxSumSubarray(arr,3)); // 9
}
}
#include <stdio.h>
int maxSumSubarray(int arr[], int n, int k) {
int currentSum = 0;
for (int i = 0; i < k; i++)
currentSum += arr[i];
int maxSum = currentSum;
for (int i = 0; i maxSum)
maxSum = currentSum;
}
return maxSum;
}
int main() {
int arr[] = {2,1,5,1,3,2};
printf("%d\n", maxSumSubarray(arr,6,3)); // 9
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int maxSumSubarray(vector<int> arr, int k) {
int currentSum = 0;
for (int i = 0; i < k; i++)
currentSum += arr[i];
int maxSum = currentSum;
for (int i = 0; i < arr.size() - k; i++) {
currentSum = currentSum - arr[i] + arr[i+k];
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
int main() {
vector<int> arr = {2,1,5,1,3,2};
cout << maxSumSubarray(arr,3); // 9
return 0;
}
Complexity Analysis
- Time Complexity: O(N). We pass through the array once. (Brute force would be O(N times K)).
- Space Complexity: O(1).
Use Cases
- String Problems: Finding the longest substring without repeating characters.
- Analytics: Moving averages (e.g., “average stock price over the last 30 days”).