Sliding Window Introduction
What is Sliding Window?
Sliding window is a technique that maintains a window (subarray/substring) and slides it across the data structure.
Visual Example
Find max sum of 3 consecutive elements:
arr = [1, 3, 2, 6, -1, 4, 1, 8, 2]
k = 3
Window 1: [1, 3, 2] 6 -1 4 1 8 2 sum = 6
↑-----↑
Window 2: 1 [3, 2, 6] -1 4 1 8 2 sum = 11
↑-----↑
Window 3: 1 3 [2, 6, -1] 4 1 8 2 sum = 7
↑-----↑
... and so on
Why It Works
Instead of recalculating from scratch for each window:
- Add the new element entering the window
- Remove the old element leaving the window
This gives O(1) update per window.
Two Types
- Fixed-size window: Window size is constant (k)
- Variable-size window: Window size changes based on condition
When to Use
- Subarray problems with contiguous elements
- Maximum/minimum sum of k elements
- Longest substring with condition
- Shortest substring with condition
Fixed-Size Window
Template
int fixedWindow(int[] arr, int k) {
// 1. Initialize window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
// 2. Slide the window
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;
}
Example: Max Sum Subarray of Size K
public int maxSum(int[] arr, int k) {
int n = arr.length;
if (n < k) return -1;
// 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 < n; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
// Time: O(n), Space: O(1)
Dry Run
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 4
Initial window: [1, 4, 2, 10] → sum = 17
Slide 1: add 2, remove 1 → [4, 2, 10, 2] → sum = 18
Slide 2: add 3, remove 4 → [2, 10, 2, 3] → sum = 17
Slide 3: add 1, remove 2 → [10, 2, 3, 1] → sum = 16
Slide 4: add 0, remove 10 → [2, 3, 1, 0] → sum = 6
Slide 5: add 20, remove 2 → [3, 1, 0, 20] → sum = 24
Max sum = 24
Complexity
- Time: O(n) - single pass
- Space: O(1) - only variables
Variable-Size Window
Template
int variableWindow(int[] arr, int target) {
int left = 0;
int windowSum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < arr.length; right++) {
// 1. Expand: add element to window
windowSum += arr[right];
// 2. Contract: remove elements from left
while (windowSum >= target) {
minLen = Math.min(minLen, right - left + 1);
windowSum -= arr[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
Example: Minimum Size Subarray Sum (LeetCode 209)
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
// Time: O(n), Space: O(1)
Dry Run
nums = [2,3,1,2,4,3], target = 7
right=0: sum=2, < 7
right=1: sum=5, < 7
right=2: sum=6, < 7
right=3: sum=8, >= 7 → minLen=4, sum=6
right=4: sum=10, >= 7 → minLen=4, sum=6, sum=4
right=5: sum=7, >= 7 → minLen=3, sum=4
Output: 3
When to Use Variable Window
- "Longest substring with at most K distinct characters"
- "Minimum window containing target"
- "Subarray with sum >= target"
- "Longest substring without repeating characters"
Sliding Window Patterns
Pattern 1: Maximum/Minimum of Size K
// Max of each window of size k
int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
int max = nums[i];
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
result[i] = max;
}
return result;
}
// Time: O(n × k) - can optimize with deque to O(n)
Pattern 2: Longest Substring with K Distinct Characters
public int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
map.merge(s.charAt(right), 1, Integer::sum);
while (map.size() > k) {
char leftChar = s.charAt(left);
map.merge(leftChar, -1, Integer::sum);
if (map.get(leftChar) == 0) map.remove(leftChar);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Time: O(n), Space: O(k)
Pattern 3: Longest Substring Without Repeating Characters (LeetCode 3)
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right))) {
left = Math.max(left, map.get(s.charAt(right)) + 1);
}
map.put(s.charAt(right), right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Time: O(n), Space: O(min(n, alphabet size))
Pattern 4: Permutation in String (LeetCode 567)
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] s1Count = new int[26];
int[] s2Count = new int[26];
for (int i = 0; i < s1.length(); i++) {
s1Count[s1.charAt(i) - 'a']++;
s2Count[s2.charAt(i) - 'a']++;
}
if (Arrays.equals(s1Count, s2Count)) return true;
for (int i = s1.length(); i < s2.length(); i++) {
s2Count[s2.charAt(i) - 'a']++;
s2Count[s2.charAt(i - s1.length()) - 'a']--;
if (Arrays.equals(s1Count, s2Count)) return true;
}
return false;
}
// Time: O(n), Space: O(1)
When to Use Each Pattern
| Problem Type | Pattern |
|---|---|
| Fixed size | Fixed window |
| Min/max subarray | Variable window |
| K distinct chars | HashMap + window |
| Permutation check | Frequency array + window |
Interactive Visualization
Sliding Window Maximum Sum
Practice Problems
You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy and a single day to sell in the future.
Example:
Input: prices = [7,1,5,3,6,4]
Output: 5
Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Edge Cases:
- All decreasing prices: return 0
- All same prices: return 0
- Two elements: return max(0, prices[1]-prices[0])
- Single element: return 0
Find the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb"
Output: 3
The answer is "abc" with length 3.
Edge Cases:
- Empty string returns 0
- Single character returns 1
- All same characters returns 1
- All unique characters returns string length
- String with spaces and special characters
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string.
Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
The minimum window substring 'BANC' includes 'A', 'B', and 'C' from string t.
Edge Cases:
- t longer than s: return empty
- s == t: return s
- No valid window exists: return empty
- t has all unique characters: simpler window tracking
Given two strings s1 and s2, return true if any permutation of s1 is a substring of s2.
Example:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
"ba" is a permutation of "ab" and is a substring.
Edge Cases:
- s1 longer than s2 — always false
- s1 and s2 same length — check if s2 is a permutation of s1
- All characters same in s1
- s1 has unique characters vs repeated characters
- No valid window exists
Find the maximum profit from buying and selling a stock once.
Example:
Input: prices = [7,1,5,3,6,4]
Output: 5
Buy on day 2 (price=1), sell on day 5 (price=6).
Edge Cases:
- All decreasing: return 0
- Single element: return 0
- All same: return 0
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window.
Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
The minimum window substring 'BANC' includes 'A', 'B', and 'C' from string t.
Edge Cases:
- t longer than s: return empty
- s == t: return s
- No valid window: return empty
Quiz
1. What is the time complexity of the fixed-size sliding window?
2. When should you use a variable-size window?
3. How do you update the window when sliding?
Flashcards
Question
What is the sliding window technique?
Click to reveal answer
Answer
Maintain a window and slide it across the array, updating in O(1) by adding new and removing old elements.
Question
Fixed vs variable window?
Click to reveal answer
Answer
Fixed: constant window size. Variable: window grows/shrinks based on condition.
Question
What problems use sliding window?
Click to reveal answer
Answer
Max sum subarray, longest substring with K distinct, minimum window substring, anagram search.
Revision Notes
Key Takeaways
- 1. Sliding window reduces O(n²) to O(n) for contiguous subarray problems
- 2. Fixed window: constant size, simple add/remove
- 3. Variable window: grow until condition, then shrink
- 4. Use HashMap for character/window problems
- 5. Always check if sliding window applies before using nested loops
Interview Tips
- • Ask if subarray must be contiguous
- • Clarify if window size is fixed or variable
- • Discuss time complexity improvement
- • Handle edge cases: empty array, single element
Cheat Sheet
Sliding Window Cheat Sheet
Fixed Window:
// Initialize first window
for (int i = 0; i < k; i++) window += arr[i];
// Slide
for (int i = k; i < n; i++) {
window += arr[i] - arr[i-k];
}
Variable Window:
for (int right = 0; right < n; right++) {
// expand
while (condition) {
// contract
left++;
}
}
Time: O(n) for both
Space: O(1) or O(k) for HashMap