Maximum Sum Subarray of Size K

Problem Overview

Given an array and a fixed window size k, find the maximum sum among all contiguous subarrays of exactly length k.

Why solve this?

The clean introductory fixed-size sliding window: recomputing every window's sum from scratch is O(n*k), but each window only differs from the last by one element leaving and one entering, so the sum can be updated in O(1) per slide.

Pattern Recognition

Whenever a fixed-size window slides one position at a time across an array and you're tempted to resum the whole window every step, track a running window sum and update it incrementally: add the incoming element, subtract the outgoing one.

Prerequisites

• Running Sum of 1d Array — the same running-total habit, now bounded to a fixed-width window instead of the whole array.

Hints

1. Summing every window of size k from scratch costs O(k) per window, O(n*k) overall — wasteful, since consecutive windows share all but two elements.
2. Compute the sum of the very first window of size k directly, once.
3. To slide the window forward by one position, add the new element entering on the right and subtract the element leaving on the left — no need to touch the elements that stayed.

Approach

Compute the sum of the first window (indices 0 through k-1) directly by adding up its k elements — this is the only part of the algorithm that costs O(k). Track this as the current window sum and also as the best sum seen so far. Then slide the window one position at a time from index k to the end of the array: at each step, add the element now entering the window on the right and subtract the element that just left on the left, producing the new window's sum in O(1). Compare it to the best sum seen so far and keep the larger. By the end of the scan, every window of size k has been considered in O(n) total time rather than O(n*k).

Code

class Solution {
    public int maxSumSubarrayOfSizeK(int[] nums, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        int best = windowSum;
        for (int i = k; i < nums.length; i++) {
            windowSum += nums[i] - nums[i - k];
            best = Math.max(best, windowSum);
        }
        return best;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy