sko.kr
  • Home
  • Blog
  • Algorithms - 1. Sliding Window (Fixed Size)

Algorithms - 1. Sliding Window (Fixed Size)

algorithmssliding-windowarraysoptimizationtwo-pointers
By sko•9/27/2025•5 min read

When to use Fixed-Size Sliding Window

Use fixed-size sliding window when you need to find optimal contiguous subarrays of a specific size. While the size constraint seems limiting, this pattern appears frequently:

  • Maximum/minimum sum of k consecutive elements (classic use case)
  • Average of k consecutive elements
  • Pattern matching with fixed-length patterns (like finding anagrams)
  • Rolling hash for substring matching
  • Time series analysis with fixed time windows (e.g., 7-day moving average)
  • Any problem requiring analysis of all subarrays of size k

Example problem

Maximum Sum of K Elements: Given daily sales revenue [100, 200, 300, 400, 100, 200, 50], find the best 3-consecutive-day period with highest total revenue.

  • Days [0-2]: 100 + 200 + 300 = 600
  • Days [1-3]: 200 + 300 + 400 = 900 ✓ Best period
  • Days [2-4]: 300 + 400 + 100 = 800
  • Days [3-5]: 400 + 100 + 200 = 700
  • Days [4-6]: 100 + 200 + 50 = 350

Answer: Days 1-3 had the highest total revenue of $900.

Single most important insight

Reuse overlapping computation - adjacent windows of size k share k-1 common elements, differing only in one element that exits and one that enters, so instead of recalculating everything we just update these two changes, achieving O(n) instead of O(n*k) complexity.

Mental note: The algorithm's genius lies in recognizing that adjacent windows overlap significantly. For a window of size 3, moving it forward means 2 elements stay the same - only the leftmost exits and a new rightmost enters. Instead of recalculating from scratch, we maintain a running state and update it incrementally. One subtraction, one addition - that's all it takes to "slide" to the next window.

Decision Framework

At every slide of the window, you perform two operations:

  • Remove the contribution of the element exiting the window (left side)
  • Add the contribution of the element entering the window (right side)

Code

// Note: We use for loop (not while) because:
// - In fixed-size sliding window, we process each element exactly once
// - Right pointer always increments by 1
// - For loop is cleaner and prevents forgetting right++

// Fixed window of EXACTLY size k
// We need to examine every possible k-sized window
function maxSumOfK(nums: number[], k: number): number {
  if (nums.length < k) return -1;

  let windowSum = 0;
  let maxSum = -Infinity;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // Add current element to window
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // DECISION FRAMEWORK: maintain window of exactly size k
    const windowSize = right - left + 1;
    // Process when window is exactly k, then slide it
    if (windowSize === k) {
      maxSum = Math.max(maxSum, windowSum);
      // Slide the window for next iteration
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

  return maxSum;
}

// Fixed window of AT MOST size k
// Duplicates "within k distance" means we need a window that never exceeds k
function hasDuplicateWithinK(nums: number[], k: number): boolean {
  const window = new Set<number>();
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // DECISION FRAMEWORK: maintain window size <= k
    // Why different from above? "Within k distance" means at most k elements apart
    // So we maintain a fixed window that grows to k, then slides at size k
    const windowSize = right - left + 1;
    const windowExceedsK = windowSize > k;
    if (windowExceedsK) {
      const elementLeavingWindow = nums[left];
      window.delete(elementLeavingWindow);
      left++;
    }

    // Check for duplicate in current window
    const currentElement = nums[right];
    const isDuplicate = window.has(currentElement);

    if (isDuplicate) {
      return true;
    }

    // Add current element to window
    window.add(currentElement);
  }

  return false;
}

Doubt buster

Common doubt: "Why track the window sum? Can't I just use nested loops to sum each window of k elements separately?"

Why you might think nested loops are fine

Consider finding the maximum sum in [100, 200, 300, 400, 100, 200, 50] with k=3:

  • "I can use outer loop for starting position, inner loop to sum k elements"
  • "For each starting position i, sum from i to i+k-1"
  • "It's only 3 elements, so the inner loop is small"
  • "The code is more intuitive - I can see exactly what's being summed"

Why this thinking is inefficient

Key realization: Nested loops recalculate the same elements repeatedly!

Let's trace [100, 200, 300, 400, 100, 200, 50] with k=3:

Nested Loop Approach (O(n*k)):
Window [0-2]: 100 + 200 + 300 = 600    (3 additions)
Window [1-3]: 200 + 300 + 400 = 900    (3 additions)
Window [2-4]: 300 + 400 + 100 = 800    (3 additions)
Window [3-5]: 400 + 100 + 200 = 700    (3 additions)
Window [4-6]: 100 + 200 + 50 = 350     (3 additions)
Total: 15 additions

Sliding Window (O(n)):
Initial [0-2]: 100 + 200 + 300 = 600   (3 additions)
Slide to [1-3]: 600 - 100 + 400 = 900  (1 subtraction, 1 addition)
Slide to [2-4]: 900 - 200 + 100 = 800  (1 subtraction, 1 addition)
Slide to [3-5]: 800 - 300 + 200 = 700  (1 subtraction, 1 addition)
Slide to [4-6]: 700 - 400 + 50 = 350   (1 subtraction, 1 addition)
Total: 3 additions + 4 subtractions + 4 additions = 11 operations

Notice that elements like 300 are added 3 times in nested loops, but only once in sliding window!

Concrete example: The scaling problem

For finding maximum sum in an array of 10,000 elements with k=1000:

Nested loops:

  • Each window: Sum 1000 elements
  • Total windows: 9001
  • Total additions: 9,001,000

Sliding Window:

  • Initial window: 1000 additions
  • Each slide: 1 subtraction + 1 addition
  • Total operations: 1000 + (9000 × 2) = 19,000
  • 474x faster!

Why the optimization matters

The sliding window technique:

  • Reuses the overlapping computation (k-1 elements stay the same)
  • Each element is added exactly once and subtracted exactly once
  • No redundant calculations of the same elements
  • Transforms O(n×k) nested loop solution to O(n) sliding window

The key insight: when moving the window one position, only 2 elements change (one leaves, one enters), so why recalculate everything?

← Back to Blog