The Sliding Window Technique: One Template for LeetCode

Sliding window is one of the most common patterns in coding interviews. If a problem asks for the longest, shortest or best contiguous subarray or substring under some rule, think sliding window first.

Three kinds of windows

1. Fixed size: the window is always k long (for example, the max sum of any k numbers in a row).
2. Growing and shrinking: the window grows on the right and shrinks on the left when a rule breaks.
3. Growing and shrinking, plus a helper: same as above, but you also keep a hash map, a count or a deque.

(session clip at 1:08)

The template

The right edge moves forward in an outer loop. When the window breaks the rule, an inner while loop moves the left edge until the window is valid again. Then you record the answer.

def sliding_window(items):
    left = 0
    state = ...                       # counts, sum, etc.
    best = 0
    for right, x in enumerate(items):
        add x to state
        while window is not valid:
            remove items[left] from state
            left += 1
        best = max(best, right - left + 1)
    return best

Every item enters the window once and leaves once, so this runs in O(n) time. (template walkthrough at 75:58)

Example 1: Longest substring without repeating characters (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:
    count = {}
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:          # a repeat: shrink from the left
            count[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Example 2: Minimum size subarray sum (LeetCode 209)

Here we want the shortest window, so we record the answer inside the shrinking loop.

def minSubArrayLen(target: int, nums: list[int]) -> int:
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

When the template breaks: negative numbers

The template works because adding an item never makes the window “less valid” in the wrong direction. With negative numbers that is no longer true: shrinking can make the sum bigger. For problems like Shortest Subarray with Sum at Least K (LeetCode 862), switch to prefix sums and a monotonic deque. (session clip at 1:50)

from collections import deque

def shortestSubarray(nums: list[int], k: int) -> int:
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    dq = deque()                       # indexes with increasing prefix sums
    best = float("inf")
    for i, p in enumerate(prefix):
        while dq and p - prefix[dq[0]] >= k:
            best = min(best, i - dq.popleft())
        while dq and prefix[dq[-1]] >= p:
            dq.pop()
        dq.append(i)
    return -1 if best == float("inf") else best

All three solutions were checked against brute force on thousands of random inputs.

Practice problems

Video walkthroughs

Sliding window template (SDE Skills algorithm session)

Sliding window with negative numbers

Practice with others, free

SDE Skills is a volunteer-run 501(c)(3) nonprofit with free daily LeetCode practice on Zoom. See the schedule and the free DSA practice sheet.

Join a session on Zoom Join our free Discord