iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Sliding Window

By · Reviewed & last updated · Part of Data Structures & Algorithms

Sliding window is the technique for problems that ask for a best subarray or substring under a constraint. Instead of recomputing each window from scratch, maintain a running aggregate and advance two pointers (left, right). Most problems are O(n) once you see the window shape.

Three canonical sliding-window problems

EXAMPLE
def max_sum_subarray(nums, k):
    '''Maximum sum of any contiguous subarray of length k.'''
    if len(nums) < k: return 0
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        if window > best: best = window
    return best

def longest_unique_substring(s):
    '''Longest substring with no repeated characters.'''
    last = {}        # char -> last index seen
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

def min_window_subarray_sum(nums, target):
    '''Shortest contiguous subarray whose sum >= target (positive nums).'''
    left = 0; 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

print(max_sum_subarray([1, 4, 2, 10, 23, 3, 1, 0, 20], 4))   # 39
print(longest_unique_substring('abcabcbb'))                  # 3
print(min_window_subarray_sum([2, 3, 1, 2, 4, 3], 7))        # 2

Why it matters

Variable-size windows (problems 2 and 3) shrink the window when an invariant is violated; fixed-size windows (problem 1) advance both ends in lockstep. Spotting which kind you have is the first step — the code falls out from there.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// Longest substring of distinct chars.
function longest(s) {
    const seen = new Map();
    let best = 0, l = 0;
    for (let r = 0; r < s.length; r++) {
        if (seen.has(s[r]) && seen.get(s[r]) >= l) l = seen.get(s[r]) + 1;
        seen.set(s[r], r);
        best = Math.max(best, r - l + 1);
    }
    return best;
}
Try it Yourself »

Discussion

Loading…