Sliding window (variable)

How does Sliding window (variable) work?

The window starts empty, with both ends at index zero. A counter or a map describes what it holds.

The right end steps forward and takes in one element. Update the description with that element.

Check the condition against the current window. While it holds, record the width or the count.

When it breaks, the left end steps forward. Remove that element from the description.

Keep shrinking until the condition holds again. Only then does the right end move on.

Neither end ever steps back. So every element enters once and leaves once.

1. window = aLongest stretch with no repeated letter. The best is 1.
2. window = abb enters and is new. The best becomes 2.
3. window = abcc enters and is new. The best becomes 3.
4. window = abcbA second b enters. The window now holds b twice.
5. window = cbThe left end drops a and the first b. The best stays 3.

function longestUnder(arr, limit) {
    let left = 0;
    let sum = 0;
    let best = 0;
    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum > limit) {
            sum -= arr[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

function longestUnder(arr: number[], limit: number): number {
    let left = 0;
    let sum = 0;
    let best = 0;
    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum > limit) {
            sum -= arr[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

def longest_under(arr, limit):
    left = 0
    total = 0
    best = 0
    for right, x in enumerate(arr):
        total += x
        while total > limit:
            total -= arr[left]
            left += 1
        best = max(best, right - left + 1)
    return best

function longestUnder(array $arr, int $limit): int {
    $left = 0;
    $sum = 0;
    $best = 0;
    for ($right = 0; $right < count($arr); $right++) {
        $sum += $arr[$right];
        while ($sum > $limit) {
            $sum -= $arr[$left];
            $left++;
        }
        $best = max($best, $right - $left + 1);
    }
    return $best;
}

    public static int longestUnder(int[] arr, int limit) {
        int left = 0;
        int sum = 0;
        int best = 0;
        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];
            while (sum > limit) {
                sum -= arr[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static int LongestUnder(int[] arr, int limit) {
        int left = 0;
        int sum = 0;
        int best = 0;
        for (int right = 0; right < arr.Length; right++) {
            sum += arr[right];
            while (sum > limit) {
                sum -= arr[left];
                left++;
            }
            best = Math.Max(best, right - left + 1);
        }
        return best;
    }

A worked example of Sliding window (variable)

Longest stretch with k distinct characters

You get a string and a number k. Find the longest stretch that uses at most k different characters.

The stretch has to be contiguous, not scattered.

Grow the window to the right and count each character in a map.

Once the map holds more than k keys, shrink from the left. Measure the width after every shrink.

function longestKDistinct(s, k) {
    const count = new Map();
    let left = 0;
    let best = 0;

    for (let right = 0; right < s.length; right++) {
        count.set(s[right], (count.get(s[right]) ?? 0) + 1);

        while (count.size > k) {
            const out = s[left];
            count.set(out, count.get(out) - 1);
            if (count.get(out) === 0) count.delete(out); // the key must go, not just the count
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

When should you use Sliding window (variable)?

Use Sliding window (variable) when the problem statement says “longest/shortest contiguous subarray or substring”, “satisfying a condition (sum <= K, at most, without breaking a limit)” or “at most K distinct, no repeated element, contains all of X”. A solution built on it usually runs in O(n).

• •longest/shortest contiguous subarray or substring
• •satisfying a condition (sum <= K, at most, without breaking a limit)
• •at most K distinct, no repeated element, contains all of X
• •contiguous span, not a subsequence

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Sliding window (variable) confused with?

Sliding window (variable) is most often confused with Sliding window (fixed size), Two pointers (opposite ends), Prefix sums and Hash set / map.

• Sliding window (fixed size): A fixed window is k wide from the first step to the last. This one picks its own width.
• Two pointers (opposite ends): Those start apart on sorted data and converge to one pair. Here both ends move the same way.
• Prefix sums: Prefix sums handle negative values and arbitrary ranges. Shrinking assumes removing a value helps.
• Hash set / map: A map on its own describes the whole collection. The window needs counts for the live span.

Common mistakes with Sliding window (variable)

• Leaving a zero count in the map

  The size still counts a key whose count fell to zero. Delete the key when it empties.

• Shrinking with an if instead of a while

  One removal may not be enough to restore the condition. Shrink until it holds again.

• Using it where values can be negative

  Dropping a value from the left may raise the sum. Then shrinking proves nothing.

• Measuring the width wrong

  The width is right minus left plus one. Dropping the plus one loses a character.

Which interview problems use Sliding window (variable)?

Interview problems solved with Sliding window (variable) include Longest substring without repeating characters, Minimum size subarray sum, Longest substring with at most k distinct characters, Longest repeating character replacement, Minimum window substring, Fruit into baskets and Max consecutive ones III.

• Longest substring without repeating characters: Shrink until the duplicate letter is gone.
• Minimum size subarray sum: Grow until the sum is enough, then shrink while it stays enough.
• Longest substring with at most k distinct characters: The map size is the condition.
• Longest repeating character replacement: Width minus the most common count must stay under k.
• Minimum window substring: Grow until every needed letter is covered, then tighten.
• Fruit into baskets: At most two distinct types, the same shape as k distinct.
• Max consecutive ones III: Shrink once the window holds more than k zeroes.

What is the time and space complexity of Sliding window (variable)?

The target complexity of Sliding window (variable) is O(n).

n up to 1e6 and one best span gives O(n). Each end advances at most n times.