Sliding Window: Harder Problems
The Sliding Window lesson covered a window tracked by one running number, a sum, a minimum, a single count. Picture that same train of connected cars, but now the conductor also has to track something more detailed about the 3 cars in view: how many different colors are among them, or whether at most 2 of them are red. This lesson covers exactly that: windows that need a whole frequency count instead of one number, and windows that must satisfy more than one rule at once. This is the pattern behind most "longest/shortest substring or subarray with property X" interview questions once they get past the beginner stage.
Fixed window with data structures
Picture a security guard watching the last 4 people to badge through a door, keeping a running tally of how many different departments are among those 4. When a 5th person badges in, the guard does not recount all 4 people from scratch: they add the new person's department to the tally and remove the department of whoever just aged out the back of the window. A fixed-size window slides the same way, one element at a time. Instead of just a running sum, you often keep a frequency map or count that updates incrementally as elements enter and leave.
from collections import Counter
def max_distinct_in_window(nums: list[int], k: int) -> int:
counts = Counter(nums[:k])
best = len(counts)
for i in range(k, len(nums)):
counts[nums[i]] += 1 # element entering
left = nums[i - k]
counts[left] -= 1 # element leaving
if counts[left] == 0:
del counts[left] # keep the map accurate for len() checks
best = max(best, len(counts))
return bestEvery fixed-window problem does exactly two things per step: add the incoming element's effect, remove the outgoing element's effect. That "effect" can be a sum, a frequency count, a max-tracking deque, or anything else you can maintain incrementally. Never recompute the whole window from scratch each step, since that turns an O(n) sliding window into O(n·k).
Remember: a fixed window does two things per step, add the new element's effect, remove the old element's effect. Never rescan the whole window.
Variable window tracking multiple conditions
Picture that same guard, but now with two rules at once: "let at most 2 departments through together, and never let the group at the door grow past 15 people." The guard still does the same two things as before, let people in from the front, remove people from the back only when a rule breaks, just checking two rules instead of one. A variable-size window grows by advancing right and shrinks by advancing left, expanding while a condition holds and contracting when it is violated. The harder version tracks several conditions at once, for example "at most 2 distinct characters and window length under some bound."
def variable_window_skeleton(s: str, is_valid) -> int:
left = 0
best = 0
window_state = {} # whatever data the condition needs: counts, max-freq, etc.
for right in range(len(s)):
# 1. expand: absorb s[right] into window_state
window_state[s[right]] = window_state.get(s[right], 0) + 1
# 2. contract while the window violates the condition
while not is_valid(window_state, right - left + 1):
window_state[s[left]] -= 1
if window_state[s[left]] == 0:
del window_state[s[left]]
left += 1
# 3. record the best valid window at this right boundary
best = max(best, right - left + 1)
return bestThe invariant to hold onto: left only ever moves forward. It never resets to 0 and rescans. That is what makes the whole algorithm O(n) instead of O(n²): each index enters and leaves the window at most once across the entire run.
Remember:
is_validcan check any number of conditions at once, the expand/contract skeleton around it never changes.
Longest Repeating Character Replacement
Intuition: You can change up to k characters in a window to make every character the same. A window is valid if window_length - count_of_most_frequent_char <= k, which is exactly the number of characters you would need to replace.
Approach: Expand right, tracking a frequency count and the running max frequency seen. max_freq never needs to decrease even as the window shrinks. It only ever underestimates slightly, but that is safe, since the answer only grows when a new max_freq is achieved, so a stale max_freq cannot produce a wrong, too-large answer. Shrink left only when the window becomes invalid.
def characterReplacement(s: str, k: int) -> int:
counts = {}
left = 0
max_freq = 0
best = 0
for right in range(len(s)):
counts[s[right]] = counts.get(s[right], 0) + 1
max_freq = max(max_freq, counts[s[right]])
window_len = right - left + 1
if window_len - max_freq > k:
counts[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestComplexity: Time O(n), space O(1) (at most 26 letters in counts).
Common mistakes: Trying to decrement max_freq when the window shrinks is unnecessary, and actually breaks the O(n) guarantee if done with a full rescan. Also, forgetting that best can be computed from the window length even mid-shrink, since the window never needs to shrink below the best length found so far; it can only stay the same or grow.
Remember:
max_freqnever needs to shrink, even when the window does. The answer can only grow.
Fruit Into Baskets
Intuition: This is "longest subarray with at most 2 distinct values" wearing a word problem's clothes. Two baskets means at most 2 distinct fruit types in the window.
Approach: Expand right, tracking fruit-type counts in a map. While the map has more than 2 keys, shrink left.
def totalFruit(fruits: list[int]) -> int:
counts = {}
left = 0
best = 0
for right, fruit in enumerate(fruits):
counts[fruit] = counts.get(fruit, 0) + 1
while len(counts) > 2:
left_fruit = fruits[left]
counts[left_fruit] -= 1
if counts[left_fruit] == 0:
del counts[left_fruit]
left += 1
best = max(best, right - left + 1)
return bestComplexity: Time O(n), space O(1) (at most 3 keys in counts at any moment, since you shrink the instant it hits 3).
Common mistakes: Not recognizing the "2 baskets" framing as "at most 2 distinct values." Translating a word problem into the underlying pattern is the real skill being tested. Also, forgetting to delete zero-count entries from the map, which corrupts the len(counts) > 2 check.
Remember: "2 baskets" is just "at most 2 distinct values" in a costume. Learn to spot the pattern under the wording.
Minimum Size Subarray Sum
Intuition: Find the shortest contiguous subarray with sum at least target. This flips the usual "maximize the window" pattern into "minimize the window while a condition holds," but the two-pointer mechanics are identical.
Approach: Expand right, adding to a running sum. While the sum meets or exceeds target, record the window length and shrink left, continuing to shrink while it is still valid, since a smaller valid window is always better here.
def minSubArrayLen(target: int, nums: list[int]) -> int:
left = 0
total = 0
best = float('inf')
for right, num in enumerate(nums):
total += num
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return best if best != float('inf') else 0Complexity: Time O(n), space O(1).
Common mistakes: Using if instead of while when shrinking. A single conditional shrink misses shorter valid windows that stay valid after one shrink step. Also, forgetting the "no valid subarray exists" case, which needs to return 0, not inf or -1.
Remember: when minimizing, shrink with a
while, not anif, and record the answer on every shrink, not just once.
Longest Subarray with Ones after Replacement
Also known as Max Consecutive Ones III (LeetCode 1004), the array version of Longest Repeating Character Replacement.
Intuition: You can flip up to k zeros to ones. Find the longest subarray you can make this way. This is structurally identical to Longest Repeating Character Replacement: a window is valid if zero_count_in_window <= k.
Approach: Expand right, tracking the count of zeros in the window. Shrink left while the zero count exceeds k.
def longestOnes(nums: list[int], k: int) -> int:
left = 0
zero_count = 0
best = 0
for right, num in enumerate(nums):
if num == 0:
zero_count += 1
while zero_count > k:
if nums[left] == 0:
zero_count -= 1
left += 1
best = max(best, right - left + 1)
return bestComplexity: Time O(n), space O(1).
Common mistakes: Building a full frequency map when a simple zero counter is enough. Only two values exist here, 0 and 1, so there is no need for a map, unlike the character-replacement version with 26 possible letters. Also, off-by-one when computing window length after the shrink loop exits.
Step back, and the four problems above split into just two templates: "at most K distinct" (Fruit Into Baskets) and "longest valid window after up to K changes" (Character Replacement, Max Consecutive Ones III). Minimum Size Subarray Sum is the mirror image of both, shrinking instead of growing. Once you can name which template a new problem matches, the two-pointer skeleton writes itself.
Remember: four problems, two templates. Name the template first, then the code is mechanical.