The sliding window technique turns many “best contiguous subarray or substring” problems from O(n^2) or O(n*k) into O(n). You keep a window over the array, defined by a left and a right index, and update a running summary (a sum, a count, a set of characters) as the window moves, instead of recomputing it from scratch. This guide gives you the test for when it applies, a template for each of the two kinds of window, worked examples that have been run, and the cases where it fails.<\/p>\n
Look for all three signs:<\/p>\n
The third point is the one people skip, and it is why sliding window does not always work with negative numbers (more on that below).<\/p>\n
The window always has k elements. Compute the first window, then for each step add the new element on the right and remove the one that fell off on the left.<\/p>\n
Maximum sum of any k consecutive elements.<\/strong> The brute force sums k numbers at each of n-k+1 positions. The window does one addition and one subtraction per step.<\/p>\n The same shape computes a moving average (divide by k), the number of vowels in every k-length substring, or whether any window of length k contains a duplicate. Time O(n), space O(1).<\/p>\n The window grows and shrinks. The template has a right pointer that advances every step, and a left pointer that advances only while the window is invalid (for “longest” problems) or while it is still valid (for “shortest” problems).<\/p>\n That is pseudocode, so it does not run as written. The next three examples fill it in.<\/p>\n Store the last index at which each character was seen. When the new character was seen inside the current window, jump the left edge just past that earlier occurrence.<\/p>\n The check Keep counts in a dictionary. When the number of distinct keys exceeds K, remove characters from the left, deleting a key when its count reaches zero.<\/p>\n For “aabacbebebe” with K = 3 the answer is 7 (“cbebebe”). Each index enters the window once and leaves at most once, so the total work is O(n) even though there is a loop inside the loop. That is the part people find surprising, and it is the point of the technique. Practice it with the Longest Subarray with at most K Distinct Integers<\/a> lesson.<\/p>\n For “shortest” problems the roles flip: shrink while the window is still valid, recording the length each time.<\/p>\n The answer for the first call is 2 (the subarray [4, 3]). Try the related Longest Subarray with Sum at most S<\/a> lesson.<\/p>\n A running sum is easy to update. A running maximum<\/em> is not, because when the maximum leaves the window you need the next largest. A deque of indexes, kept in decreasing order of value, solves it: before adding a new index, pop smaller values off the back (they can never be the maximum while the new one is in the window), and pop the front when it leaves the window.<\/p>\n Each index is pushed and popped at most once, so this is O(n). A heap also works but costs O(n log n).<\/p>\n The shrink-while-valid trick relies on monotonic behavior. With negative numbers, a sum can go up after you add an element and down after you remove one, so shrinking the window from the left no longer reliably finds the answer. Here is a case where the shortest-subarray function above is wrong:<\/p>\n Running the window function on this input returns 5 while the correct answer is 3. For arrays with negative numbers, use prefix sums with a hash map (for “sum exactly k”) or a monotonic deque over prefix sums (for “shortest with sum at least k”). Here is the hash-map version, which counts subarrays with a given sum and works with negatives:<\/p>\n Other non-fits: problems about subsequences (the elements need not be adjacent), and conditions you cannot update in O(1) per move.<\/p>\n With O(1) updates, each pointer moves forward at most n times, so the time is O(n), compared with O(n^2) for checking every subarray. Space is O(1) for a running sum or counter, O(min(n, alphabet size)) for a dictionary of characters, and O(k) for the deque.<\/p>\n The Sliding Window Technique lesson<\/a> on AlgoCademy walks through these steps interactively, and our post on sliding window for coding interviews<\/a> covers more interview-style problems.<\/p>\n","protected":false},"excerpt":{"rendered":" Learn the sliding window technique: when to use fixed and variable windows, a reusable template, five tested Python examples, and the mistakes that cause bugs.<\/p>\n","protected":false},"author":1,"featured_media":4522,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-4523","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4523"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=4523"}],"version-history":[{"count":1,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4523\/revisions"}],"predecessor-version":[{"id":8720,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/4523\/revisions\/8720"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/4522"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=4523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=4523"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=4523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}def max_sum_k(nums, k):\n if k <= 0 or len(nums) < k:\n return None\n s = best = sum(nums[:k])\n for i in range(k, len(nums)):\n s += nums[i] - nums[i - k] # add the new one, drop the old one\n best = max(best, s)\n return best\n\nprint(max_sum_k([2, 1, 5, 1, 3, 2], 3), max_sum_k([1], 3))\n# 9 None<\/code><\/pre>\nType 2: variable-size window<\/h2>\n
def longest_valid(items):\n left = 0\n best = 0\n state = ... # counts, sum, set, whatever the condition needs\n for right, x in enumerate(items):\n add x to state\n while window is invalid:\n remove items[left] from state\n left += 1\n best = max(best, right - left + 1)\n return best<\/code><\/pre>\nLongest substring without repeating characters<\/h3>\n
def longest_no_repeat(s):\n last, start, best = {}, 0, 0\n for end, ch in enumerate(s):\n if ch in last and last[ch] >= start:\n start = last[ch] + 1\n last[ch] = end\n best = max(best, end - start + 1)\n return best\n\nprint(longest_no_repeat(\"abcabcbb\"), longest_no_repeat(\"pwwkew\"), longest_no_repeat(\"\"))\n# 3 3 0<\/code><\/pre>\nlast[ch] >= start<\/code> is the detail that matters: a character seen before the window began does not count, and without that check the window can move backwards.<\/p>\nLongest substring with at most K distinct characters<\/h3>\n
def longest_k_distinct(s, k):\n counts, start, best = {}, 0, 0\n for end, ch in enumerate(s):\n counts[ch] = counts.get(ch, 0) + 1\n while len(counts) > k:\n counts[s[start]] -= 1\n if counts[s[start]] == 0:\n del counts[s[start]]\n start += 1\n best = max(best, end - start + 1)\n return best\n\nprint(longest_k_distinct(\"aabacbebebe\", 3), longest_k_distinct(\"abc\", 0))\n# 7 0<\/code><\/pre>\nShortest subarray with sum at least target (positive numbers)<\/h3>\n
def min_len_sum_at_least(nums, target):\n start = total = 0\n best = float(\"inf\")\n for end, x in enumerate(nums):\n total += x\n while total >= target:\n best = min(best, end - start + 1)\n total -= nums[start]\n start += 1\n return 0 if best == float(\"inf\") else best\n\nprint(min_len_sum_at_least([2, 3, 1, 2, 4, 3], 7), min_len_sum_at_least([1, 1], 5))\n# 2 0<\/code><\/pre>\nWindow maximum with a monotonic deque<\/h2>\n
from collections import deque\n\ndef sliding_max(nums, k):\n dq, out = deque(), [] # indexes; nums[dq[0]] is the window max\n for i, x in enumerate(nums):\n while dq and nums[dq[-1]] <= x:\n dq.pop()\n dq.append(i)\n if dq[0] <= i - k:\n dq.popleft()\n if i >= k - 1:\n out.append(nums[dq[0]])\n return out\n\nprint(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))\n# [3, 3, 5, 5, 6, 7]<\/code><\/pre>\nWhen sliding window does NOT work<\/h2>\n
nums, target = [84, -37, 32, 40, 95], 167\n# window version (min_len_sum_at_least) returns 5\n# brute force finds [32, 40, 95] = 167, length 3<\/code><\/pre>\ndef count_sub_sum_k(nums, k):\n seen = {0: 1} # prefix sum -> times seen\n s = count = 0\n for x in nums:\n s += x\n count += seen.get(s - k, 0)\n seen[s] = seen.get(s, 0) + 1\n return count\n\nprint(count_sub_sum_k([1, 2, 3], 3), count_sub_sum_k([1, -1, 1, 1], 2))\n# 2 2<\/code><\/pre>\nCommon mistakes<\/h2>\n
\n
right - left + 1<\/code> when both ends are inclusive. Write it down once and reuse it.<\/li>\nleft<\/code>, or forgetting to delete a key whose count dropped to zero (this breaks “distinct” checks).<\/li>\nif<\/code> instead of while<\/code><\/strong> to shrink. One new element can force several removals.<\/li>\nComplexity<\/h2>\n
How to practice<\/h2>\n
\n