Speed Up the Sliding Window Sum

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

function maxWindowSum(nums, k) {
  let best = -Infinity;
  for (let start = 0; start + k <= nums.length; start++) {
    let sum = 0;
    for (let i = start; i < start + k; i++) sum += nums[i];
    best = Math.max(best, sum);
  }
  return best;
}

function maxWindowSum(nums: number[], k: number): number {
  let best = -Infinity;
  for (let start = 0; start + k <= nums.length; start++) {
    let sum = 0;
    for (let i = start; i < start + k; i++) sum += nums[i];
    best = Math.max(best, sum);
  }
  return best;
}

def max_window_sum(nums: list[int], k: int) -> int:
    best = None
    for start in range(len(nums) - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        best = total if best is None else max(best, total)
    return best

<?php

function maxWindowSum(array $nums, int $k): int
{
    $best = PHP_INT_MIN;
    $n = count($nums);
    for ($start = 0; $start + $k <= $n; $start++) {
        $sum = 0;
        for ($i = $start; $i < $start + $k; $i++) {
            $sum += $nums[$i];
        }
        $best = max($best, $sum);
    }
    return $best;
}

class Solution {
    public int maxWindowSum(int[] nums, int k) {
        int best = Integer.MIN_VALUE;
        for (int start = 0; start + k <= nums.length; start++) {
            int sum = 0;
            for (int i = start; i < start + k; i++) sum += nums[i];
            best = Math.max(best, sum);
        }
        return best;
    }
}

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Why it is slow: (n - k + 1) windows x k additions each, about 1.6 billion additions here.

The fix: sum the first window once, then slide: for each next position add the value entering the window and subtract the one leaving it. Every value is added once and removed once: O(n) total, independent of k.

Optimized solution

function maxWindowSum(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]; // value entering minus value leaving
    best = Math.max(best, sum);
  }
  return best;
}

function maxWindowSum(nums: number[], k: number): number {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k]; // value entering minus value leaving
    best = Math.max(best, sum);
  }
  return best;
}

def max_window_sum(nums: list[int], k: int) -> int:
    total = best = sum(nums[:k])
    for i in range(k, len(nums)):
        total += nums[i] - nums[i - k]  # value entering minus value leaving
        best = max(best, total)
    return best

<?php

function maxWindowSum(array $nums, int $k): int
{
    $sum = array_sum(array_slice($nums, 0, $k));
    $best = $sum;
    $n = count($nums);
    for ($i = $k; $i < $n; $i++) {
        $sum += $nums[$i] - $nums[$i - $k]; // value entering minus value leaving
        $best = max($best, $sum);
    }
    return $best;
}

class Solution {
    public int maxWindowSum(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += nums[i];
        int best = sum;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k]; // value entering minus value leaving
            best = Math.max(best, sum);
        }
        return best;
    }
}

Common mistakes

Initialising the answer to 0 instead of the first window's sum (all-negative input).
Off-by-one on the value that leaves the window (i - k).

Follow-up questions

Maximum value (not sum) in each window: a monotonic deque.
Variable-size window: shortest subarray with sum at least S.

Example 1

Constraints

The slow code

Hints

Make it faster

Solution and explanation

Optimized solution

Common mistakes

Follow-up questions

Example 1

Constraints

The slow code

Hints

Make it faster

Solution and explanation

Optimized solution

Common mistakes

Follow-up questions

More Code Clinic: Make It Fast problems