Sliding window is a technique where we maintain a “window” (a contiguous subarray or substring) and slide it across the data. Instead of recalculating everything from scratch for each position, we update the window incrementally — add the new element, remove the old one.
In simple language, imagine looking through a picture frame that we slide across a wall of photos. We don’t re-examine every photo each time — we just note what entered the frame and what left it.
Why It’s Efficient
The brute force approach to “find the best subarray of size k” checks every possible subarray — that’s O(n * k). With sliding window, we process each element at most twice (once when it enters the window, once when it leaves). That gives us O(n).
Two Types of Windows
Fixed-Size Window: Max Sum Subarray of Size K
Given an array and a number k, find the subarray of size k with the maximum sum. We compute the sum of the first window, then slide it — subtract the element that leaves, add the element that enters.
function maxSumSubarray(arr, k) {
// build the first window
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += arr[i];
}
let maxSum = windowSum;
// slide the window: remove left element, add right element
for (let i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k]; // add new, remove old
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// maxSumSubarray([2, 1, 5, 1, 3, 2], 3) => 9 (5 + 1 + 3)def max_sum_subarray(arr, k):
# build the first window
window_sum = sum(arr[:k])
max_sum = window_sum
# slide the window: remove left element, add right element
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k] # add new, remove old
max_sum = max(max_sum, window_sum)
return max_sum
# max_sum_subarray([2, 1, 5, 1, 3, 2], 3) => 9 (5 + 1 + 3)static int maxSumSubarray(int[] arr, int k) {
// build the first window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
// slide the window: remove left element, add right element
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k]; // add new, remove old
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// maxSumSubarray([2, 1, 5, 1, 3, 2], 3) => 9 (5 + 1 + 3)Time: O(n), Space: O(1). Each element is visited exactly once. The brute force approach (recomputing the sum for each window) would be O(n * k).
Variable-Size Window: Longest Substring Without Repeating Characters
This is one of the most popular interview questions (LeetCode #3). We expand the window by moving the right pointer. When we hit a duplicate character, we shrink the window from the left until the duplicate is removed.
function lengthOfLongestSubstring(s) {
const seen = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
// shrink window until no duplicate
while (seen.has(s[right])) {
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// lengthOfLongestSubstring("abcabcbb") => 3 ("abc")
// lengthOfLongestSubstring("bbbbb") => 1 ("b")def length_of_longest_substring(s):
seen = set()
left = 0
max_len = 0
for right in range(len(s)):
# shrink window until no duplicate
while s[right] in seen:
seen.discard(s[left])
left += 1
seen.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
# length_of_longest_substring("abcabcbb") => 3 ("abc")
# length_of_longest_substring("bbbbb") => 1 ("b")static int lengthOfLongestSubstring(String s) {
Set<Character> seen = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
// shrink window until no duplicate
while (seen.contains(s.charAt(right))) {
seen.remove(s.charAt(left));
left++;
}
seen.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// lengthOfLongestSubstring("abcabcbb") => 3 ("abc")Time: O(n), Space: O(min(n, alphabet_size)). Each character enters and leaves the set at most once, so the inner while loop doesn’t make this O(n²) — it’s amortized O(n).
Sliding Window Template
Most variable-size window problems follow the same structure. Here’s the template:
function slidingWindow(arr) {
let left = 0;
let result = 0; // or Infinity, depending on min/max
for (let right = 0; right < arr.length; right++) {
// 1. Expand: add arr[right] to our window state
// 2. Shrink: while window is invalid, remove arr[left]
while (/* window is invalid */) {
// remove arr[left] from window state
left++;
}
// 3. Update: record the best answer so far
result = Math.max(result, right - left + 1);
}
return result;
}def sliding_window(arr):
left = 0
result = 0 # or float('inf'), depending on min/max
for right in range(len(arr)):
# 1. Expand: add arr[right] to our window state
# 2. Shrink: while window is invalid, remove arr[left]
while True: # window is invalid
# remove arr[left] from window state
left += 1
break # replace with actual condition
# 3. Update: record the best answer so far
result = max(result, right - left + 1)
return resultstatic int slidingWindow(int[] arr) {
int left = 0;
int result = 0; // or Integer.MAX_VALUE for min problems
for (int right = 0; right < arr.length; right++) {
// 1. Expand: add arr[right] to our window state
// 2. Shrink: while window is invalid, remove arr[left]
while (/* window is invalid */) {
// remove arr[left] from window state
left++;
}
// 3. Update: record the best answer so far
result = Math.max(result, right - left + 1);
}
return result;
}The three steps are always the same: expand the right side, shrink the left side when the window becomes invalid, and update the result. The only difference between problems is what “invalid” means and what state we track.
Fixed vs Variable: When to Use Which
| Fixed-Size Window | Variable-Size Window |
|---|---|
| Window size k is given in the problem | We’re looking for the longest/shortest subarray |
| ”Subarray of size k" | "Smallest subarray with sum >= target” |
| Slide by exactly 1 each step | Left pointer moves only when window is invalid |
| Usually simpler to implement | Needs a condition to shrink/expand |
How to Recognize a Sliding Window Problem
Look for these clues:
- The problem asks about contiguous subarrays or substrings
- Words like “maximum”, “minimum”, “longest”, “shortest” paired with a subarray constraint
- We need to find something optimal within a range of elements
- The brute force would involve checking all possible subarrays (O(n²) or worse)
The only difference between sliding window and two pointers is that sliding window specifically deals with contiguous elements (subarrays/substrings), while two pointers is more general.
In simple language, if the problem says “contiguous subarray” and “find the best one”, sliding window is almost always the answer. We just need to figure out whether it’s fixed-size or variable-size, and what condition controls the window.