Slide a Fixed Window

Practice Exercise Interview Easy Fixed-size Window

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement fixed_window_sums(values, width). Return the sum of every contiguous window of exactly width values from left to right. width is positive; return an empty list when width is larger than the input.

Starter code

def fixed_window_sums(values, width):
    pass

Test cases

three-wide

{
  "args": [
    [
      2,
      1,
      5,
      1,
      3
    ],
    3
  ]
}

Expected: [8,7,9]

unit-width

{
  "args": [
    [
      4,
      -2,
      7
    ],
    1
  ]
}

Expected: [4,-2,7]

Wizard outline

Step 1: Reject an impossible window
Return no sums when width exceeds the input length. A fixed window must contain exactly width values, so this guard prevents invalid initialization.
Step 2: Compute the first complete window
Create the initial total and result entry. Every rolling update depends on the total for values[:width].
Step 3: Advance a one-item window
Move the boundary while replacing the leaving value with the entering value. Width one makes the add-minus-remove update visible with the smallest possible state.
Step 4: Slide every fixed-width window
Generalize the rolling update to any valid positive width. The same entering-minus-leaving invariant holds for every fixed window size.

Footguns and prerequisites

Removing the outgoing value at right - width + 1 drops a current member instead of the previous window member.
A width larger than the input has no complete window and must not emit a partial sum.
arrays strings two pointers sliding window

Reviewed references

Python deque Recipes

Prepared Interview Problems

K-Radius Subarray Averages(opens in a new tab)
Slide a Fixed Window isolates before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. That focused state discipline is required when implementing k radius subarray averages as a complete Interview Problem.
Maximum Sum of a Distinct Length-K Subarray(opens in a new tab)
Slide a Fixed Window isolates before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. That focused state discipline is required when implementing max sum distinct length k as a complete Interview Problem.
Permutation in String(opens in a new tab)
Slide a Fixed Window isolates before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. That focused state discipline is required when implementing permutation in string as a complete Interview Problem.

Recommended approach and implementation

When every candidate segment has the same width, reuse the previous aggregate instead of recomputing each segment. Before appending a result, the rolling total contains exactly values[right - width + 1:right + 1].

Why it works: The first total covers exactly the first width values. Each slide removes the value leaving the window and adds the value entering it, so every appended total belongs to the requested contiguous window.

def fixed_window_sums(values, width):
    if width > len(values):
        return []
    total = sum(values[:width])
    result = [total]
    for right in range(width, len(values)):
        total += values[right] - values[right - width]
        result.append(total)
    return result