Step 3 · DSA
Spot it in ten seconds
⏰
Round 2 of an off-campus test. Aarav gets "longest substring without repeating characters". He writes two nested loops, hits Run, and 41 of 60 cases pass. The rest say Time Limit Exceeded. His logic was right. His loop count was wrong.
A sliding window replaces those two loops with one. Instead of building every subarray from scratch, you keep one window alive and move it: the element on the right joins, the element on the left leaves. Nothing is counted twice.
The three signals
The answer is a contiguous subarray or substringThe words "subarray", "substring", "consecutive", "in a row". Not "subsequence", not "any k elements".
It asks for the longest, shortest, maximum, minimum, or a count"Longest substring with...", "minimum size subarray such that...", "how many subarrays have...".
There is exactly one rule the window must obeyExactly k long. At most k distinct letters. Sum at least 7. No repeated character.
Contiguous, plus a best-or-count question, plus one rule. All three present? Slide a window. n up to 100000 in the constraints is the final confirmation.
Template
Shape 1 · The fixed window
The width never changes. Every step, one element joins on the right and one leaves on the left. Here is the window on [2, 1, 5, 1, 3, 2] with k = 3.
index 0 1 2 3 4 5
value 2 1 5 1 3 2
step 1 [ 2 1 5 ] 1 3 2 sum = 8
step 2 2 [ 1 5 1 ] 3 2 sum = 7
step 3 2 1 [ 5 1 3 ] 2 sum = 9 best
step 4 2 1 5 [ 1 3 2 ] sum = 6
# Python
window = 0
best = 0
for right in range(len(nums)):
window += nums[right] # the new element joins
if right >= k - 1:
best = max(best, window) # window is exactly k wide
window -= nums[right - k + 1] # the oldest element leaves
// Java
int window = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
window += nums[right]; // the new element joins
if (right >= k - 1) {
best = Math.max(best, window); // window is exactly k wide
window -= nums[right - k + 1]; // the oldest element leaves
}
}
Read the index arithmetic once and never again: when the right edge sits at right, the left edge sits at right - k + 1. The window is full for the first time when right reaches k - 1.
Template
Shape 2 · The growing window
Here the width changes. The right edge always moves forward. The left edge moves only when the window breaks the rule. Below: the shortest block with sum at least 7.
nums = [2, 3, 1, 2, 4, 3] rule: sum >= 7
grow [2 3 1 2] 4 3 sum 8 ok, length 4
shrink 2 [3 1 2] 4 3 sum 6 broken, grow again
grow 2 [3 1 2 4] 3 sum 10 ok, length 4
shrink 2 3 [1 2 4] 3 sum 7 ok, length 3
shrink 2 3 1 [2 4] 3 sum 6 broken, grow again
grow 2 3 1 [2 4 3] sum 9 ok, length 3
shrink 2 3 1 2 [4 3] sum 7 ok, length 2
# Python
left = 0
best = 0
for right in range(len(nums)):
# 1. let nums[right] into the window (update sum / set / map)
while window_breaks_the_rule():
# 2. push nums[left] out - undo exactly what step 1 did
left += 1
# 3. the window is legal now, so update the answer
best = max(best, right - left + 1)
// Java
int left = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
// 1. let nums[right] in
while (windowBreaksTheRule()) {
// 2. push nums[left] out
left++;
}
best = Math.max(best, right - left + 1); // 3. legal, so record
}
Why is this O(n) when there is a loop inside a loop? Because left never goes backwards. Over the whole run right takes n steps and left takes at most n steps.
Problem 1 EASY
Max sum subarray of size k
Given an array and a number k, find the biggest sum you can make from k numbers sitting next to each other.
Brute force: start at every index and add up the next k numbers. That is n starts times k additions; at n = 100000 and k = 1000 it is 100 million. Too slow.
Window insight: the block [i .. i+k-1] and the next block share k-1 numbers. Do not add them twice. Subtract the one that left, add the one that arrived.
# Python
def max_sum_k(nums, k):
window = 0
best = 0
for right in range(len(nums)):
window += nums[right]
if right >= k - 1:
best = max(best, window)
window -= nums[right - k + 1]
return best
// Java
static int maxSumK(int[] nums, int k) {
int window = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
window += nums[right];
if (right >= k - 1) {
best = Math.max(best, window);
window -= nums[right - k + 1];
}
}
return best;
}
nums = [2, 1, 5, 1, 3, 2] k = 3 answer 9 O(n) time, O(1) space
right joins sum full window best then leaves
0 +2 2 - -
1 +1 3 - -
2 +5 8 [2 1 5] 8 2
3 +1 7 [1 5 1] 8 1
4 +3 9 [5 1 3] 9 5
5 +2 6 [1 3 2] 9 1
Problem 2 MEDIUM
Longest substring, no repeats
Find the length of the longest stretch in which no character appears twice. In "pwwkew" the answer is 3, from "wke".
Brute force: from every start, walk right with a set until a repeat appears. About n squared / 2 checks; at n = 100000 that is 5 billion. Too slow.
Window insight: keep a set of what is inside. If the arriving character is already in the set, shrink from the left until it is gone, then add it.
# Python
def longest_unique(s):
seen = set()
left = 0
best = 0
for right in range(len(s)):
while s[right] in seen: # while, never if
seen.remove(s[left])
left += 1
seen.add(s[right])
best = max(best, right - left + 1)
return best
// Java - needs java.util.Set and java.util.HashSet
static int longestUnique(String s) {
Set<Character> seen = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
while (seen.contains(s.charAt(right))) {
seen.remove(s.charAt(left));
left++;
}
seen.add(s.charAt(right));
best = Math.max(best, right - left + 1);
}
return best;
}
s = "pwwkew" answer 3 O(n) time, O(k) space for the set
right char left window best
0 p 0 "p" 1
1 w 0 "pw" 2
2 w 2 "w" 2 left jumped past the old w
3 k 2 "wk" 2
4 e 2 "wke" 3
5 w 3 "kew" 3
Problem 3 MEDIUM
At most k distinct
Longest stretch that uses at most k different characters. In "eceba" with k = 2 the answer is 3, from "ece". Brute force: O(n squared).
Window insight: use a count map, not a set - a character can repeat inside. Map size is the distinct count. Delete a key when its count hits zero.
# Python
def at_most_k_distinct(s, k):
count = {}
left = 0
best = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
while len(count) > k:
c = s[left]
count[c] -= 1
if count[c] == 0: del count[c] # or the size lies
left += 1
best = max(best, right - left + 1)
return best
// Java - needs java.util.Map and java.util.HashMap
static int atMostKDistinct(String s, int k) {
Map<Character, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
count.put(c, count.getOrDefault(c, 0) + 1);
while (count.size() > k) {
char out = s.charAt(left);
count.put(out, count.get(out) - 1);
if (count.get(out) == 0) count.remove(out);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
s = "eceba" k = 2 answer 3 O(n) time, O(k) space
right char map after adding shrink window best
0 e {e:1} no "e" 1
1 c {e:1, c:1} no "ec" 2
2 e {e:2, c:1} no "ece" 3
3 b {e:2, c:1, b:1} drop e, drop c "eb" 3
4 a {e:1, b:1, a:1} drop e "ba" 3
Problem 4 MEDIUM
Shortest subarray with sum at least target
All numbers positive. Find the shortest block with sum at least target, or 0 if none. Target 7, [2, 3, 1, 2, 4, 3] gives 2, from [4, 3].
Brute force tries every start and end: O(n squared). Window insight: this asks for the shortest, so record inside the shrink loop, not after it.
# Python
def min_subarray_len(target, nums):
left = 0
total = 0
best = len(nums) + 1 # impossible marker
for right in range(len(nums)):
total += nums[right]
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == len(nums) + 1 else best
// Java
static int minSubarrayLen(int target, int[] nums) {
int left = 0, total = 0;
int best = nums.length + 1;
for (int right = 0; right < nums.length; right++) {
total += nums[right];
while (total >= target) {
best = Math.min(best, right - left + 1);
total -= nums[left];
left++;
}
}
return best == nums.length + 1 ? 0 : best;
}
target = 7 nums = [2, 3, 1, 2, 4, 3] answer 2 O(n) time
right joins sum shrink steps while sum >= 7 best
0 +2 2 - -
1 +3 5 - -
2 +1 6 - -
3 +2 8 [2 3 1 2] len 4, drop 2, sum 6 4
4 +4 10 [3 1 2 4] len 4, drop 3, sum 7
[1 2 4] len 3, drop 1, sum 6 3
5 +3 9 [2 4 3] len 3, drop 2, sum 7
[4 3] len 2, drop 4, sum 3 2
Problem 5 MEDIUM
Permutation in a string
Is any rearrangement of the pattern present in the text as one block? "ab" is inside "eidbaooo" (the "ba"), not inside "eidboaoo".
Brute force: every permutation of the pattern - ten letters gives 3.6 million. Window insight: a permutation is just a bag of letters, so slide a fixed window of the pattern's length and compare 26 counters.
# Python - lowercase letters only
def check_inclusion(pattern, text):
m, n = len(pattern), len(text)
if m > n: return False
need, have = [0] * 26, [0] * 26
for i in range(m): # first window
need[ord(pattern[i]) - 97] += 1
have[ord(text[i]) - 97] += 1
if need == have: return True
for right in range(m, n):
have[ord(text[right]) - 97] += 1 # joins
have[ord(text[right - m]) - 97] -= 1 # leaves
if need == have: return True
return False
// Java - needs java.util.Arrays
static boolean checkInclusion(String pattern, String text) {
int m = pattern.length(), n = text.length();
if (m > n) return false;
int[] need = new int[26], have = new int[26];
for (int i = 0; i < m; i++) {
need[pattern.charAt(i) - 'a']++;
have[text.charAt(i) - 'a']++;
}
if (Arrays.equals(need, have)) return true;
for (int right = m; right < n; right++) {
have[text.charAt(right) - 'a']++;
have[text.charAt(right - m) - 'a']--;
if (Arrays.equals(need, have)) return true;
}
return false;
}
pattern "ab", need {a:1, b:1} text "eidbaooo" O(26n) time
window have counts joins leaves match?
"ei" {e:1, i:1} - - no
"id" {i:1, d:1} d e no
"db" {d:1, b:1} b i no
"ba" {b:1, a:1} a d YES, return true
Debug list
The five mistakes
When a window solution fails on case 34 of 60, it is almost always one of these five. Check them in this order.
1. Shrinking with if instead of whileOne removal is often not enough. On "pwwkew" at the second w you must drop p and then w. An if drops only p, leaves the duplicate inside, and returns an answer bigger than the truth.
2. Updating the answer at the wrong momentLooking for the longest? Update after the shrink loop, when the window is legal again. Looking for the shortest? Update inside the shrink loop, while it is still legal. Swapping these two is the most common wrong answer in this pattern.
3. Forgetting to remove the element that leftEvery add in step 1 needs an exact undo in step 2. Do count[c] += 1 on the way in but never count[c] -= 1 on the way out and the window never becomes legal again. And when a count reaches zero, delete the key, or the map keeps counting a character that has already gone.
4. Using a window on a non-contiguous problem"Longest increasing subsequence", "pick any k elements", "the two numbers can be anywhere" - a window cannot help. Elements you skip still sit inside the window's range, so the window means nothing. That is a sorting, hash map or DP problem.
5. Resetting the window instead of sliding itWriting left = right and clearing the whole set on a violation throws away work that was still valid. On "abcabcbb" it happens to give the right 3; on "abac" it gives 2 when the answer is 3, from "bac". Move the left edge one step at a time. Never rebuild.
Revision card
All five on one page
The night before a test, read only this. Each row is: which shape, what you carry inside the window, and when you touch the answer.
Problem
Shape
Carry inside
Update
Max sum of size k
Fixed, k
Running sum
When full
Longest, no repeats
Growing
Set of characters
After shrink
At most k distinct
Growing
Count map; size = distinct
After shrink
Shortest, sum >= target
Growing
Running sum
Inside shrink
Permutation in a string
Fixed, m
Two arrays of 26 counts
Every step
Longest: record afterwhile broken:
shrink()
best = max(best,
right - left + 1)
Shortest: record insidewhile good:
best = min(best,
right - left + 1)
shrink()
Every one of these is O(n). Say that out loud in the interview, then say why: the left edge never moves backwards.