Contents
- What is Sliding Window?
- Fixed-size Sliding Window
- Dynamic (Variable) Sliding Window
- When to use Sliding Window
- Complexity
Consider having an array or string and being asked a question about a contiguous subarray or substring —
for example, the maximum sum of any k consecutive elements. A brute-force approach
would use two nested loops and run in O(n·k) time.
The Sliding Window technique eliminates this redundant work by maintaining a window
defined by two pointers — left and right — and sliding this window
across the array, updating the result incrementally rather than recomputing it from scratch each time.
There are two main variants:
- Fixed-size window — the window size k is constant. Both pointers move together.
- Dynamic (variable) window — the window size changes based on a condition. The right pointer expands the window; the left pointer shrinks it when the condition is violated.
In a fixed-size window, the window always contains exactly k elements. As the window slides
right by one position, the rightmost element enters and the leftmost element leaves.
Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9 (subarray [5, 1, 3])
Sliding Window O(n) approach:
public int maxSumFixedWindow(int[] nums, int k) {
int windowSum = 0;
// Compute sum of first window
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
int maxSum = windowSum;
// Slide the window: add right element, remove left element
for (int i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
Complexity:
- Time: O(n) — single pass through the array.
- Space: O(1) — no extra space needed.
In a dynamic window, the window expands by moving right forward and shrinks by moving
left forward whenever a constraint is violated. This is the more common variant
used in string/substring problems.
Input: nums = [2, 3, 1, 2, 4, 3], target = 7
Output: 2 (subarray [4, 3])
public int minSubArrayLen(int target, int[] nums) {
int left = 0, windowSum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
windowSum += nums[right]; // expand window
// Shrink window from left while condition is satisfied
while (windowSum >= target) {
minLen = Math.min(minLen, right - left + 1);
windowSum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
General template for dynamic sliding window:
int left = 0;
// some window state (e.g. sum, frequency map)
for (int right = 0; right < n; right++) {
// 1. Add element at right to the window state
// 2. Shrink window from left if constraint is violated
while (/* window is invalid */) {
// Remove element at left from window state
left++;
}
// 3. Update answer with current valid window [left, right]
}
Sliding window is a strong fit when the problem asks about:
- Maximum or minimum of a contiguous subarray or substring of fixed or variable length.
- Longest or shortest substring satisfying a condition (e.g. at most k distinct chars).
- Counting subarrays that meet a criterion (e.g. sum equals k).
- Problems involving contiguous elements — not arbitrary subsets.
Sliding window only works when the problem has the monotonic property — expanding the window
makes it "more valid" (or "more invalid") in one direction only. If shrinking from the left can both help
and hurt the condition, a different technique is needed.
-
Time complexity: O(n) — each element is added to the window once and removed at most once,
so the total number of operations is O(2n) = O(n).
-
Space complexity: O(1) to O(k) — O(1) for simple sum-based windows;
O(k) when using a frequency map (e.g. for character-count windows).