Efficiently process contiguous subarrays and substrings by maintaining a window that slides through the data.
The brute-force approach to subarray problems often recalculates everything from scratch for each position. The sliding window pattern avoids this by maintaining a "window" over a contiguous portion of the data and incrementally updating it as the window moves.
Instead of recomputing the sum of each subarray from scratch, slide a window forward: add the new element entering on the right, remove the old element leaving on the left.
Brute force: O(n * k) recomputes the sum for each window position. The sliding window does it in O(n) because each element enters and leaves the window exactly once.
Look for these recognition signals in the problem statement. If you spot one, the sliding window pattern is very likely the intended approach.
"Find the longest/shortest subarray or substring with..."
"Maximum/minimum sum of k consecutive elements"
"Contiguous sequence"
"Character frequency constraints"
Not a sliding window? If the problem asks about non-contiguous subsequences, or if the data is not linear (like a tree or graph), sliding window does not apply. Also, if the array has negative numbers, a variable-size sum window may not work because shrinking does not always increase the sum.
The window always contains exactly k elements. It slides one position to the right each step. Use this for problems like "maximum sum subarray of size k" or "moving average of last k values."
int maxSumSubarray(int[] arr, int k) { int windowSum = 0, maxSum = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { windowSum += arr[i]; // add incoming element if (i >= k - 1) { // window is full maxSum = Math.max(maxSum, windowSum); windowSum -= arr[i - k + 1]; // remove outgoing element } } return maxSum; }
Maximum sum of 3 consecutive elements = 13 at window [3, 8, 2].
The window expands to the right unconditionally and contracts from the left when a condition is violated. This finds the longest/shortest valid subarray.
int minSubarrayLen(int target, int[] arr) { int left = 0, windowSum = 0; int minLen = Integer.MAX_VALUE; for (int right = 0; right < arr.length; right++) { windowSum += arr[right]; // expand: always add right while (windowSum >= target) { // shrink while valid minLen = Math.min(minLen, right - left + 1); windowSum -= arr[left]; // remove left element left++; } } return minLen == Integer.MAX_VALUE ? 0 : minLen; }
Find the shortest subarray with sum ≥ 7.
Shortest subarray with sum ≥ 7 has length 2: the subarray [4, 3].
Why is this O(n)? Even though there is a while loop inside the for loop, each element is added at most once (when right advances) and removed at most once (when left advances). Total operations across all iterations: at most 2n.
When you need to track the frequency of elements inside the window, combine the sliding window with a hash map. This is essential for string problems like "find all anagrams" or "minimum window substring."
List<Integer> findAnagrams(String s, String p) { List<Integer> result = new ArrayList<>(); int[] need = new int[26], have = new int[26]; for (char c : p.toCharArray()) need[c - 'a']++; int left = 0, matched = 0; for (int right = 0; right < s.length(); right++) { int c = s.charAt(right) - 'a'; have[c]++; if (have[c] <= need[c]) matched++; // useful match if (right - left + 1 > p.length()) { // window too big int out = s.charAt(left) - 'a'; if (have[out] <= need[out]) matched--; have[out]--; left++; } if (matched == p.length()) // all chars matched result.add(left); } return result; }
Slide a window of size 3 and check if the frequency counts match "abc".
Anagrams of "abc" found at indices 0 and 6.
Here are the two fundamental templates you should memorize. Nearly every sliding window problem is a variation of one of these.
// Maximum sum of k consecutive elements int windowSum = 0; for (int i = 0; i < arr.length; i++) { windowSum += arr[i]; // 1. Add incoming element if (i >= k - 1) { // 2. Window has k elements? maxSum = Math.max(maxSum, windowSum); // 3. Update answer windowSum -= arr[i - k + 1]; // 4. Remove outgoing element } }
// Generic two-pointer sliding window int left = 0; for (int right = 0; right < arr.length; right++) { // 1. Expand: add arr[right] to window state while (windowIsInvalid()) { // 2. Shrink: remove arr[left] from window state left++; } // 3. Update answer with current valid window // window = arr[left..right], length = right - left + 1 }
Choosing between "shrink while invalid" vs "shrink while valid": If you want the longest valid window, shrink while invalid, then record. If you want the shortest valid window, shrink while valid and record during each shrink step.
These are the classic LeetCode problems that use the sliding window pattern. They are listed in rough order of difficulty.
Practice tip: Start with #209 (pure variable window + sum) and #3 (variable window + set). Once comfortable, tackle #76 which combines variable window with a frequency map and is considered one of the hardest medium/hard problems.
Try both window variants with your own inputs. Step through to see exactly how the window moves.
Fixed window: Each element is visited exactly once as right pointer sweeps the array. Each step does O(1) work (add one, subtract one). Total: O(n).
Variable window: The right pointer moves n times. The left pointer also moves at most n times total across all iterations (it never moves backward). So the inner while loop, summed across all outer iterations, runs at most n times. Total: O(n + n) = O(n).
Space: For pure sum-based windows, O(1). For hash map variants (character frequency), O(k) where k is the alphabet size or number of distinct elements in the pattern.
Amortized analysis: The key insight is that across the entire algorithm, each element is processed at most twice: once when the right pointer includes it, and once when the left pointer excludes it. This is why the nested loops still give linear time.
Two variants, one idea. Fixed-size windows slide rigidly. Variable-size windows expand and contract. Both avoid redundant recalculation by updating incrementally.
O(n) from the two-pointer invariant. Each element enters the window once and leaves once. The inner shrink loop is not nested cost; it is amortized across the entire traversal.
Spot the pattern by keywords. "Contiguous subarray", "substring with at most k", "consecutive elements", "longest/shortest" are all strong signals for sliding window.
Combine with hash maps for string problems. When character frequencies matter, augment the window with a frequency counter. The window still slides the same way; you just track more state.
Watch for negative numbers. Variable-size sum windows assume that expanding the window can only increase the sum (or that shrinking can only decrease it). Negative numbers break this monotonicity, and you may need a different technique like prefix sums or deque-based approaches.