NeetCode 150 · Sliding Window

Sliding Window Problems

Maintain a window over an array or string, expanding right and shrinking left to find the optimal sub-array satisfying a condition.

Problems: 6
Easy: 1
Medium: 3
Hard: 2
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Easy ArraySliding WindowGreedy
Given array prices where prices[i] is the price on day i, find the maximum profit from one buy and one sell (buy before sell). Return 0 if no profit possible.
Test Cases
maxProfit([7,1,5,3,6,4]) → 5 maxProfit([7,6,4,3,1]) → 0
track running minone-pass greedyO(n) O(1)
As you scan, keep track of the cheapest price seen so far. At each price, what's the best profit you could make selling today?
Python Solution
def maxProfit(prices): min_price = float('inf') max_profit = 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit
Key idea: Track the minimum price seen so far. At each new price, compute profit if we sold today. Update the best profit. One pass, constant space.
Time: O(n).
Space: O(1).
02 Medium StringSliding WindowHash Map
Given string s, find the length of the longest substring without repeating characters.
Test Cases
lengthOfLongestSubstring('abcabcbb') → 3 lengthOfLongestSubstring('bbbbb') → 1 lengthOfLongestSubstring('pwwkew') → 3
last_seen dictshrink left on repeatO(n)
Use a dict storing the last seen index of each character. When a repeat is found, jump the left pointer past the previous occurrence.
Python Solution
def lengthOfLongestSubstring(s): last_seen = {} left = best = 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] >= left: left = last_seen[ch] + 1 # shrink window last_seen[ch] = right best = max(best, right - left + 1) return best
Key idea: Sliding window where left is the start of the valid window. When we see a repeated character that's inside the window, jump left past it. Always update the last seen position.
Time: O(n).
Space: O(min(n,m)) where m is the alphabet size.
03 Medium StringSliding Window
Given string s and integer k, return the length of the longest substring you can get after replacing at most k characters with any letter.
Test Cases
characterReplacement('ABAB', 2) → 4 characterReplacement('AABABBA', 1) → 4
max_count trickwindow validityO(n)
A window is valid if (window_size - max_count_in_window) ≤ k. What's the key invariant about max_count as the window grows?
Python Solution
def characterReplacement(s, k): count = {} left = best = max_count = 0 for right, ch in enumerate(s): count[ch] = count.get(ch, 0) + 1 max_count = max(max_count, count[ch]) # Characters to replace = window_size - max_count if (right - left + 1) - max_count > k: count[s[left]] -= 1 left += 1 best = max(best, right - left + 1) return best
Key idea: Replacements needed = window_size - most_frequent_char_count. If replacements > k, shrink from the left. We never need to decrease max_count — if it was valid before, tracking the historical max is fine.
Time: O(n).
Space: O(1) — 26 characters max.
04 Medium StringSliding WindowHash Map
Given strings s1 and s2, return True if s2 contains a permutation of s1 (i.e., some substring of s2 is an anagram of s1).
Test Cases
checkInclusion('ab', 'eidbaooo') → True checkInclusion('ab', 'eidboaoo') → False
fixed windowCounter comparisonO(n)
A sliding window of length len(s1) across s2 — if the window's character counts match s1's counts, we found a permutation.
Python Solution
from collections import Counter def checkInclusion(s1, s2): if len(s1) > len(s2): return False need = Counter(s1) window = Counter(s2[:len(s1)]) if window == need: return True for i in range(len(s1), len(s2)): right_ch = s2[i] left_ch = s2[i - len(s1)] window[right_ch] += 1 window[left_ch] -= 1 if window[left_ch] == 0: del window[left_ch] if window == need: return True return False
Key idea: Fixed-size sliding window of length len(s1). Slide it across s2, adding the new right character and removing the old left character. Compare Counter objects at each step.
Time: O(n).
Space: O(1).
05 Hard StringSliding WindowHash Map
Given strings s and t, return the minimum window substring of s that contains every character of t. Return empty string if no such window exists.
Test Cases
minWindow('ADOBECODEBANC', 'ABC') → 'BANC' minWindow('a', 'a') → 'a' minWindow('a', 'aa') → ''
have/need trackingshrink on validvariable window
Expand right until you have all required chars. Then shrink from the left as long as the window is still valid. Track the best valid window seen.
Python Solution
from collections import Counter def minWindow(s, t): if not t: return "" need = Counter(t) window = {} formed = 0 # how many chars satisfy their required count required = len(need) # distinct chars we need left = 0 best = float('inf'), 0, 0 for right, ch in enumerate(s): window[ch] = window.get(ch, 0) + 1 if ch in need and window[ch] == need[ch]: formed += 1 while formed == required: if right - left + 1 < best[0]: best = right - left + 1, left, right lch = s[left] window[lch] -= 1 if lch in need and window[lch] < need[lch]: formed -= 1 left += 1 return "" if best[0] == float('inf') else s[best[1]:best[2] + 1]
Key idea: Two pointers. Expand right until all required characters are satisfied (formed == required). Then shrink left to minimize the window, saving the best. Repeat.
Time: O(s + t).
Space: O(s + t).
06 Hard ArraySliding WindowDeque
Given integer array nums and integer k, return an array of the maximum value in each window of size k.
Test Cases
maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3) → [3,3,5,5,6,7] maxSlidingWindow([1], 1) → [1]
monotonic dequeindex-based dequeO(n)
Use a deque that stores indices in decreasing order of their values. The front is always the max. Remove indices that fall outside the window.
Python Solution
from collections import deque def maxSlidingWindow(nums, k): dq = deque() # stores indices; nums[dq[0]] is always the window max result = [] for i, n in enumerate(nums): # Remove indices outside the window while dq and dq[0] <= i - k: dq.popleft() # Remove indices whose values are smaller than current while dq and nums[dq[-1]] < n: dq.pop() dq.append(i) if i >= k - 1: result.append(nums[dq[0]]) return result
Key idea: A monotonic deque maintains candidate indices in decreasing value order. The front is the current window max. As we slide right, pop from the back anything smaller than the new element (they can never be a future max).
Time: O(n) — each index pushed/popped once.
Space: O(k).
← Prev Category Next Category →