Sliding Window Basics
Imagine you have a window that slides over an array, covering a contiguous block of elements. At each position, you need to compute something (sum, max, etc.). Sliding window technique efficiently solves such problems in O(n) by reusing calculations.
Common pattern: find maximum sum of any subarray of fixed size k.
public static int maxSumFixedWindow(int[] arr, int k) {
// Compute sum of first window
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
// Slide the window
for (int i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
Variable-size sliding window
Sometimes window size is not fixed; we need to find longest subarray satisfying a condition (e.g., sum <= target).
public static int longestSubarraySumAtMost(int[] arr, int target) {
int left = 0, sum = 0, maxLen = 0;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum > target) {
sum -= arr[left];
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
Sliding window is widely used for substring problems, longest subarray with sum constraints, and many others.
Two Minute Drill
- Sliding window optimizes O(n²) brute-force to O(n).
- Fixed-size window: maintain sum by removing leftmost and adding rightmost.
- Variable-size window: expand right, shrink left when condition violated.
- Used for max/min sums, substring patterns, longest subarray, etc.
Need more clarification?
Drop us an email at career@quipoinfotech.com