FAANGPrep Sprint

Overview (Fixed Length)

Master the fixed-size sliding window pattern: slide one element out, slide one element in.

Medium

15 min

What is a Fixed Length Window?

In a Fixed Length sliding window, the size of the window k never changes. Visualizing it is simple: imagine a rigid frame of size k sliding across your array one step at a time.

The Golden Rule:
At each step, we do exactly two things in O(1) time:

Remove the element leaving the window (the one at i - k).
Add the element entering the window (the one at i).

This "Add-Remove" strategy avoids re-calculating the window content from scratch, turning an O(N*K) brute force algorithm into an O(N) linear solution.

Core Problem: Maximum Sum Subarray of Size K

The classic problem to learn this pattern:

Given an array of integers nums and an integer k, find the maximum sum of any contiguous subarray of size k.

Example:

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray [5, 1, 3] has the largest sum.

The LeetCode problem linked above, 643. Maximum Average Subarray I, asks for the maximum average of a length-k subarray. It uses exactly the same windows: this lesson computes the maximum sum, and the answer to 643 is bestSum / k.

Algorithm Strategy

Initialize: Calculate the sum of the first k elements. Set this as your initial current_sum and max_sum.
Slide: Iterate from index k to the end of the array.
Update: For each new element at index i:
- Add nums[i] to current_sum.
- Subtract nums[i - k] (the element falling out) from current_sum.
- Update max_sum = max(max_sum, current_sum).
Return: max_sum.

Visual Walkthrough

WINDOW OF 3

FIRST WINDOW

Sum

Best

—

Best ÷ k

—

First window: add nums[0] = 2. Sum 2

First window: add nums[1] = 1. Sum 3

Array

Legend & Complexity

The frame: the window of k values

The value entering, added to the sum

The value leaving, subtracted from the sum

The window with the largest sum

Time

O(n)

Space

O(1)

Watch how the window slides. Notice that we don't re-add the middle elements; we purely adjust for the entering and leaving numbers.

Dry Run: [2, 1, 5, 1, 3, 2], k=3

Step	Window Indices	Window Values	Operation	Current Sum	Max Sum
Init	`[0, 2]`	`[2, 1, 5]`	Sum first 3	`2+1+5 = 8`	8
Slide 1	`[1, 3]`	`[1, 5, 1]`	Add 1, Remove 2	`8 + 1 - 2 = 7`	8
Slide 2	`[2, 4]`	`[5, 1, 3]`	Add 3, Remove 1	`7 + 3 - 1 = 9`	9
Slide 3	`[3, 5]`	`[1, 3, 2]`	Add 2, Remove 5	`9 + 2 - 5 = 6`	9
End					Result: 9

Edge Cases & Common Mistakes

Edge Cases:

Array length < k: Checking should happen immediately. Usually return 0 or error.
k = 1: The problem reduces to finding the maximum element in the array.

Common Mistakes:

Off-by-one errors: Calculating the index of the element leaving (i - k vs i - k + 1 etc). If iterating i from 0 to end, the leaving element is i - k only after i >= k-1.
Re-summing: Using a loop inside the loop to sum the window elements, leading to O(N*K) complexity.

The Code Template

This template applies to almost any fixed-window problem (Generic inputs are used).

Overview (Fixed Length) Code

1function maxSumSubarray(nums, k) {
2    if (nums.length < k) return 0;
3    
4    let currentSum = 0;
5    for (let i = 0; i < k; i++) {
6        currentSum += nums[i];
7    }
8    
9    let maxSum = currentSum;
10    
11    for (let i = k; i < nums.length; i++) {
12        currentSum += nums[i];
13        currentSum -= nums[i - k];
14        maxSum = Math.max(maxSum, currentSum);
15    }
16    return maxSum;
17}

Previous Problem

Sort Colors

Next Problem

Longest Substring Without Repeating