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
    """
    # 1: a window needs at least one item. len(nums): it cannot be bigger.
    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])
    # (true after each update). The +1s give the k items that end at right.
    window_sum = sum(nums[:k])       # [:k]: the first window, indices 0..k-1
    best = window_sum                # the first window is the best so far

    # right: index of the item entering. Start at k: 0..k-1 are already summed.
    for right in range(k, len(nums)):
        # right - k: the item k steps back slides out on the left.
        window_sum += nums[right] - nums[right - k]
        best = max(best, window_sum) # keep the largest window sum

    return best

Walkthrough

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

Reading the figure. Blue cells are in the window. Amber is the cell entering on the right. Red is the cell leaving on the left. The green box marks the best window seen.

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 inside the window. 0: start of s
    best = 0                         # 0: right answer for an empty string

    # right: index of the newest character. Invariant at the top of each pass:
    # s[left..right-1] has no repeats, and best is the longest such run so far.
    for right, ch in enumerate(s):
        # Only a repeat *inside* the current window forces a jump.
        # >= left: an older copy before left is already outside, so ignore it.
        if ch in last_seen and last_seen[ch] >= left:
            # + 1: start just past the old copy, so ch appears once again.
            left = last_seen[ch] + 1

        last_seen[ch] = right        # remember the newest position of ch
        # + 1: right - left counts gaps. Add 1 so both ends count.
        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":

Reading the figure. Blue cells are in the window. Amber is the new character. Red cells were skipped by the jump. In the last row the saved index of a is 0, which is left of left, so it must not move left back.

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                         # 0: the window starts at the first item
    total = 0                        # 0: the sum of an empty window
    best = math.inf                  # inf: "no answer yet". Any real length beats it.

    # right: index of the newest item. Invariant at the top of each pass:
    # total == sum(nums[left:right]) and total < target.
    for right, value in enumerate(nums):
        total += value               # value joins on the right

        # The window is valid. Squeeze it from the left while it stays valid.
        while total >= target:
            # + 1: both ends count, so the length is right - left + 1.
            best = min(best, right - left + 1)
            total -= nums[left]      # the leftmost item leaves
            left += 1                # +1: the window now starts one step right

    # 0: the agreed answer when no window reaches target.
    # int(): best is still a float type because it started as math.inf.
    return 0 if best == math.inf else int(best)

Walkthrough

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

Reading the figure. Blue cells are in the window after the shrink. Red cells were dropped while the total stayed at least 7. Green is the answer window of length 2. Each record happens before the drop.

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'
    """
    # Empty input, or t longer than s: no window can hold all of t.
    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
    # 0: placeholder start. inf: "no window yet", so any real length beats it.
    best_start, best_len = 0, math.inf
    left = 0                          # 0: the window starts at the first char

    # right: index of the newest char. Invariant at the top of each pass:
    # missing > 0, so s[left..right-1] does not cover t yet.
    for right, ch in enumerate(s):
        # Grow. A positive need means this character actually pays down a debt.
        if need[ch] > 0:              # > 0: t still wants a copy of ch
            missing -= 1              # -1: one fewer required char owed
        need[ch] -= 1                 # -1: the window holds one more ch

        # Valid window. Shrink from the left while it stays valid.
        while missing == 0:           # 0: nothing owed, so the window covers t
            # + 1: both ends count. Keep this window if it is the shortest yet.
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1

            leaving = s[left]
            need[leaving] += 1        # +1: the window hands this char back
            if need[leaving] > 0:     # we just gave back a character we needed
                missing += 1          # +1: one required char is owed again
            left += 1                 # +1: the window now starts one step right

    # inf: no window ever covered t. Else take best_len chars from best_start.
    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.

Reading the figure. Violet cells are the characters of t. Each bar is a window at the moment it becomes valid, with missing == 0. Blue bars are valid but not the best. The green bar 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 "".