Sliding Window

1. Maximum Subarray of Size K Easy

Problem

Given an array of integers nums and an integer k, return the maximum sum of any contiguous subarray of length exactly k.

Approach

• The brute force sums each of the n - k + 1 windows from scratch: O(n·k).
• Two neighbouring windows differ by exactly two elements. Compute the first window once, then each later window in O(1) by adding the entering element and subtracting the leaving one.
• This is Template A with no shrink step, because the width never changes.

Solution

def max_subarray_sum_of_size_k(nums: list[int], k: int) -> int:
    """Return the largest sum of any contiguous subarray of length k.

    Args:
        nums: Input numbers. Values may be negative.
        k: Window length. Must satisfy 1 <= k <= len(nums).

    Returns:
        The maximum window sum.

    Raises:
        ValueError: If k is outside 1..len(nums).

    Example:
        >>> max_subarray_sum_of_size_k([2, 1, 5, 1, 3, 2], 3)
        9
    """
    if not 1 <= k <= len(nums):
        raise ValueError(f"k must be in 1..{len(nums)}, got {k}")

    # Invariant: window_sum == sum(nums[right - k + 1 : right + 1])
    window_sum = sum(nums[:k])
    best = window_sum

    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]
        best = max(best, window_sum)

    return best

Walkthrough

With nums = [2, 1, 5, 1, 3, 2] and k = 3:

Edge cases to raise

• k == len(nums): one window, the loop body never runs, the initial sum is the answer.
• k > len(nums): undefined. Raise rather than silently return a wrong number.
• All negatives: still correct, because best starts at the real first window, not at 0. Starting best = 0 is the classic bug here.

2. Longest Substring Without Repeating Characters Medium

Problem

Given a string s, return the length of the longest substring with no repeated characters. For "abcabcbb" the answer is 3, from "abc".

Approach

• Grow the window one character at a time. The window must always hold distinct characters.
• When the new character ch is already inside the window, the window is illegal. Every window starting at or before the previous occurrence of ch is also illegal, so jump left straight past it.
• Storing the last index of each character, instead of a set, lets the jump be a single assignment rather than a shrink loop.

Solution

def length_of_longest_substring(s: str) -> int:
    """Length of the longest substring of s with all-distinct characters.

    Args:
        s: Input string. May be empty.

    Returns:
        The length of the longest run with no repeats. 0 for an empty string.

    Example:
        >>> length_of_longest_substring("pwwkew")
        3
    """
    last_seen: dict[str, int] = {}   # character -> index of its last occurrence
    left = 0                         # first index still inside the window
    best = 0

    for right, ch in enumerate(s):
        # Only a repeat *inside* the current window forces a jump.
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1

        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

Why the >= left check matters

The dictionary remembers characters that have already fallen out of the window. Take "abba". At right = 3 the character 'a' was last seen at index 0, but left is already 2, so 'a' is not in the window and no jump is needed. Without the guard, left would move backwards to 1 and the answer would be wrong. This one comparison is what the interviewer is watching for.

Walkthrough

s = "abba":

Edge cases to raise

• Empty string returns 0; the loop never runs.
• All identical characters returns 1.
• Unicode: the dictionary handles any code point, so nothing changes. Say so, it shows care.

3. Minimum Size Subarray Sum Medium

Problem

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. Return 0 if no such subarray exists.

Approach

• Grow the window on the right, adding to a running total.
• The moment the total reaches target, the window is valid. Now shrink from the left as far as it will go while staying valid, recording the length at each step. That finds the shortest valid window ending at this right.
• This is the shortest variant, so best is updated inside the shrink loop.

Solution

import math


def min_subarray_len(target: int, nums: list[int]) -> int:
    """Shortest contiguous subarray of nums with sum >= target.

    Assumes every value in nums is positive, which is what makes the
    running total monotone in the window width and the shrink step valid.

    Args:
        target: Required minimum sum, positive.
        nums: Positive integers.

    Returns:
        The length of the shortest qualifying subarray, or 0 if there is none.

    Example:
        >>> min_subarray_len(7, [2, 3, 1, 2, 4, 3])
        2
    """
    left = 0
    total = 0
    best = math.inf

    for right, value in enumerate(nums):
        total += value

        # The window is valid; squeeze it from the left while it stays valid.
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1

    return 0 if best == math.inf else int(best)

Walkthrough

target = 7, nums = [2, 3, 1, 2, 4, 3]:

The answer is 2, from [4, 3].

The follow-up you will be asked

Edge cases to raise

• Total of the whole array is below target: best stays inf, return 0.
• A single element already reaches target: the shrink loop finds length 1.
• Empty array: returns 0.

4. Minimum Window Substring Hard

Problem

Given strings s and t, return the shortest substring of s that contains every character of t, counting repeats. Return "" if there is none. For s = "ADOBECODEBANC" and t = "ABC" the answer is "BANC".

Approach

• Same shape as the previous problem, but the summary is richer: instead of a single sum, track how many of each required character are still owed.
• need is a counter that starts as the counts in t. As characters enter the window it is decremented, so a value can go negative, meaning the window holds a surplus of that character.
• A single integer missing tracks how many required characters, counting repeats, are still unmet. The window is valid exactly when missing == 0. This is what keeps validity a O(1) test rather than a dictionary comparison.
• When valid, shrink from the left and record, exactly as in the previous problem.

Solution

import math
from collections import Counter


def min_window(s: str, t: str) -> str:
    """Shortest substring of s containing every character of t, with repeats.

    Args:
        s: The string to search.
        t: The required characters, with multiplicity.

    Returns:
        The shortest qualifying substring, or "" if none exists.

    Example:
        >>> min_window("ADOBECODEBANC", "ABC")
        'BANC'
    """
    if not s or not t or len(t) > len(s):
        return ""

    need: Counter[str] = Counter(t)   # >0 means still owed, <0 means surplus
    missing = len(t)                  # required characters not yet covered
    best_start, best_len = 0, math.inf
    left = 0

    for right, ch in enumerate(s):
        # Grow. A positive need means this character actually pays down a debt.
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        # Valid window. Shrink from the left while it stays valid.
        while missing == 0:
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1

            leaving = s[left]
            need[leaving] += 1
            if need[leaving] > 0:     # we just gave back a character we needed
                missing += 1
            left += 1

    return "" if best_len == math.inf else s[best_start : best_start + best_len]

Why the counter is allowed to go negative

This is the subtle part, and the reason the code is short. Suppose t = "AB" and the window is "AAB". Then need['A'] == -1. When the leftmost 'A' leaves, need['A'] becomes 0, which is not positive, so missing stays at 0 and the window is still valid, correctly. Only when a genuinely needed character leaves does need rise above zero and missing tick back up. The sign of the counter encodes surplus versus debt for free.

Walkthrough

s = "ADOBECODEBANC", t = "ABC". The window first becomes valid at "ADOBEC", length 6. Shrinking is blocked immediately, because dropping 'A' breaks it. Later the window "CODEBA" is valid at length 6, then "BANC" at length 4, which is the answer.

Edge cases to raise

• t longer than s: the early return handles it.
• t has repeats, such as t = "AABC": handled, because missing counts multiplicity rather than distinct characters.
• s == t: the whole string is the answer.
• No valid window: best_len stays inf and the function returns "".