beta

M5 · Sliding Window · cheat sheet

Sliding window: fixed and variable windows.

Answer questions about contiguous stretches in one pass, with a window of fixed size or one that grows and shrinks.

read the lesson ▶ watch the lecture

Spot it: the words in the question

consecutive
contiguous
in a row
stretch
run
session
window of k
longest ... such that
shortest ... at least

The invariant

The window always holds exactly the values from left to right, and its running total always equals their sum.

The pattern

Pattern cardSliding window

Use it when the question is about a contiguous stretch and asks for a best value, a count, the longest or the shortest. Signal words: consecutive, in a row, a run, a session.

Fixed window (the size k is given): build the first window of k values, then slide. Each slide adds values[right] and subtracts values[right - k].

Variable window (the size is the answer): move right on every step. While the window breaks the rule, move left. Record the answer when the window is valid.

Longest or shortest? For the longest valid window, record after the shrink loop. For the shortest window that reaches a target, record inside the shrink loop, before each value leaves.

It needs a rule that stays broken as the window grows. Non-negative values with a sum limit have this property. Negative values do not.

Cost: each value joins once and leaves at most once, so the whole pass is O(n).

Complexity

Fixed window. Building the first window takes k additions. Each slide takes two operations. That is about n operations in all, so the time is O(n).
Variable window. Right moves n times. Left also moves at most n times in total, across all the while loops together. So the loop inside a loop looks like O(n^2), but the total work is O(n).
Amortised cost. Some steps of the inner loop do a lot of work and most do none, but the total stays small. Counting the cost across the whole run like this is called amortised cost (Module 1).
Space. A few variables, so O(1) extra memory. Some practice problems keep a hash map inside the window; then the space grows with the number of different values in it.
At dashboard size. About 43,200 steps per channel, two operations each. Across 10,000 channels that is under 10^9 operations: about 9 seconds on one core, instead of 100 minutes. That fits inside the one-minute refresh, and channels can also run in parallel.

Templates · Python

The lesson’s templates, checked in all four languages against the same test cases.

Code in four languagesFixed window: the best total of k consecutive values

pythonbest_window_sum · 12 lines

def best_window_sum(values, k):
    # [1] Build the first window: the first k values.
    window = 0
    for i in range(k):
        window += values[i]
    best = window
    # [2] Slide: the value at right joins, the value at right - k leaves.
    for right in range(k, len(values)):
        window += values[right] - values[right - k]
        # [3] Keep the best total seen so far.
        best = max(best, window)
    return best

java15 lines

public long bestWindowSum(int[] values, int k) {
    // [1] Build the first window: the first k values.
    long window = 0; // 64-bit, because totals can pass 2^31
    for (int i = 0; i < k; i++) {
        window += values[i];
    }
    long best = window;
    // [2] Slide: the value at right joins, the value at right - k leaves.
    for (int right = k; right < values.length; right++) {
        window += values[right] - values[right - k];
        // [3] Keep the best total seen so far.
        best = Math.max(best, window);
    }
    return best;
}

c++15 lines

long long bestWindowSum(const vector<int>& values, int k) {
    // [1] Build the first window: the first k values.
    long long window = 0;  // 64-bit, because totals can pass 2^31
    for (int i = 0; i < k; i++) {
        window += values[i];
    }
    long long best = window;
    // [2] Slide: the value at right joins, the value at right - k leaves.
    for (int right = k; right < (int) values.size(); right++) {
        window += values[right] - values[right - k];
        // [3] Keep the best total seen so far.
        best = max(best, window);
    }
    return best;
}

javascriptbestWindowSum · 15 lines

function bestWindowSum(values, k) {
  // [1] Build the first window: the first k values.
  let window = 0;
  for (let i = 0; i < k; i++) {
    window += values[i];
  }
  let best = window;
  // [2] Slide: the value at right joins, the value at right - k leaves.
  for (let right = k; right < values.length; right++) {
    window += values[right] - values[right - k];
    // [3] Keep the best total seen so far.
    best = Math.max(best, window);
  }
  return best;
}

Code in four languagesVariable window: the longest stretch within a budget

pythonlongest_within_budget · 14 lines

def longest_within_budget(values, budget):
    left = 0
    window = 0
    best = 0
    for right in range(len(values)):
        # [1] The value at right joins the window.
        window += values[right]
        # [2] While the window breaks the rule, the value at left leaves.
        while window > budget:
            window -= values[left]
            left += 1
        # [3] The window is valid again: record its length.
        best = max(best, right - left + 1)
    return best

java17 lines

public int longestWithinBudget(int[] values, int budget) {
    int left = 0;
    long window = 0;
    int best = 0;
    for (int right = 0; right < values.length; right++) {
        // [1] The value at right joins the window.
        window += values[right];
        // [2] While the window breaks the rule, the value at left leaves.
        while (window > budget) {
            window -= values[left];
            left++;
        }
        // [3] The window is valid again: record its length.
        best = Math.max(best, right - left + 1);
    }
    return best;
}

c++17 lines

int longestWithinBudget(const vector<int>& values, int budget) {
    int left = 0;
    long long window = 0;
    int best = 0;
    for (int right = 0; right < (int) values.size(); right++) {
        // [1] The value at right joins the window.
        window += values[right];
        // [2] While the window breaks the rule, the value at left leaves.
        while (window > budget) {
            window -= values[left];
            left++;
        }
        // [3] The window is valid again: record its length.
        best = max(best, right - left + 1);
    }
    return best;
}

javascriptlongestWithinBudget · 17 lines

function longestWithinBudget(values, budget) {
  let left = 0;
  let window = 0;
  let best = 0;
  for (let right = 0; right < values.length; right++) {
    // [1] The value at right joins the window.
    window += values[right];
    // [2] While the window breaks the rule, the value at left leaves.
    while (window > budget) {
      window -= values[left];
      left++;
    }
    // [3] The window is valid again: record its length.
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Code in four languagesVariable window: the shortest stretch that reaches a target

pythonshortest_reaching_target · 15 lines

def shortest_reaching_target(values, target):
    n = len(values)
    left = 0
    window = 0
    best = n + 1
    for right in range(n):
        # [1] The value at right joins the window.
        window += values[right]
        # [2] While the window still reaches the target, record it, then the value at left leaves.
        while window >= target:
            best = min(best, right - left + 1)
            window -= values[left]
            left += 1
    # [3] If no window reached the target, report 0.
    return best if best <= n else 0

java18 lines

public int shortestReachingTarget(int[] values, long target) {
    int n = values.length;
    int left = 0;
    long window = 0;
    int best = n + 1;
    for (int right = 0; right < n; right++) {
        // [1] The value at right joins the window.
        window += values[right];
        // [2] While the window still reaches the target, record it, then the value at left leaves.
        while (window >= target) {
            best = Math.min(best, right - left + 1);
            window -= values[left];
            left++;
        }
    }
    // [3] If no window reached the target, report 0.
    return best <= n ? best : 0;
}

c++18 lines

int shortestReachingTarget(const vector<int>& values, long long target) {
    int n = values.size();
    int left = 0;
    long long window = 0;
    int best = n + 1;
    for (int right = 0; right < n; right++) {
        // [1] The value at right joins the window.
        window += values[right];
        // [2] While the window still reaches the target, record it, then the value at left leaves.
        while (window >= target) {
            best = min(best, right - left + 1);
            window -= values[left];
            left++;
        }
    }
    // [3] If no window reached the target, report 0.
    return best <= n ? best : 0;
}

javascriptshortestReachingTarget · 18 lines

function shortestReachingTarget(values, target) {
  const n = values.length;
  let left = 0;
  let window = 0;
  let best = n + 1;
  for (let right = 0; right < n; right++) {
    // [1] The value at right joins the window.
    window += values[right];
    // [2] While the window still reaches the target, record it, then the value at left leaves.
    while (window >= target) {
      best = Math.min(best, right - left + 1);
      window -= values[left];
      left++;
    }
  }
  // [3] If no window reached the target, report 0.
  return best <= n ? best : 0;
}

Pitfalls

✕ 1A variable window with negative values
Kestrel Pay wants the shortest stretch of hours with a net total of at least 167. Refunds make some hours negative.

✕ 2If instead of while

python4 lines

if window >= target:  # bug: this must be a while loop
    best = min(best, right - left + 1)
    window -= values[left]
    left += 1

Test these

The window is longer than the data
The smallest and the largest window
Negative values in a fixed window
No valid window at all

Not this pattern

Not consecutive: the three busiest hours

Sofia brings a different question from the content team: which three hours had the most play starts, even if they are not next to each other? For [4, 2, 7, 1, 8, 3], the answer is hours 4, 2 and 0, with 8, 7 and 4 thousand.

Practise it

systemdesignmastery.dev/dsa/cheatsheets/fixed-and-variable-windows