Maximum Sum Subarray of Size K

Problem Statement

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

Example 1:

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

Example 2:

Input: nums = [-3, 4, -1, 2, 1], k = 2
Output: 3
Explanation: Subarray [4, -1] has sum 3; subarray [2, 1] also has sum 3.

Constraints:

1 <= k <= nums.length <= 10^5.
-10^4 <= nums[i] <= 10^4.

Difficulty: Easy / Medium Round: OA

Pattern Recognition

What is the input structure? A flat integer array.
What are we optimizing? The maximum sum over all length-k contiguous windows.
What pattern does this fit? Fixed-size sliding window.
Why does this pattern fit? The window size is constant, so moving the window by one position is an O(1) update: add the new element entering, subtract the element leaving.

This is the purest form of sliding window. Any time the window size is fixed, the solution is O(n) with constant extra memory.

Approach

Brute Force — Recompute Each Window

For each starting index i from 0 to n - k, compute sum(nums[i..i+k-1]) and track the max.

best = -infinity
for i in 0..n-k:
    sum = 0
    for j in 0..k-1:
        sum += nums[i + j]
    best = max(best, sum)

Time: O(n * k). Space: O(1). Why insufficient: For n = 10^5 and k = n/2, this is 5 * 10^9 operations — TLE.

Optimal — Sliding Window

Key Insight: The sum of the window starting at i+1 equals the sum of the window starting at i, minus nums[i], plus nums[i+k]. Constant-time update.

Step-by-step:

Compute the sum of the first k elements. Call this windowSum. Initialize best = windowSum.
For i from k to n - 1:
- windowSum += nums[i] - nums[i - k] (slide: add new, drop old).
- best = max(best, windowSum).
Return best.

Time: O(n) — each index visited twice (once to enter, once to leave). Space: O(1).

Walkthrough

Trace on nums = [2, 1, 5, 1, 3, 2], k = 3:

Initial window sum: 2 + 1 + 5 = 8. best = 8.

i	entering (nums[i])	leaving (nums[i-k])	windowSum	best
3	1	2	8 - 2 + 1 = 7	8
4	3	1	7 - 1 + 3 = 9	9
5	2	5	9 - 5 + 2 = 6	9

Answer: 9 (window [5, 1, 3]).

Implementation

TypeScriptC++

typescript

function maxSumSubarrayOfSizeK(nums: number[], k: number): number {
    if (nums.length < k) return 0;

    // Seed the window with the first k elements.
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += nums[i];
    let best = windowSum;

    // Slide by one each iteration: add entering, subtract leaving.
    for (let i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

cpp

#include <vector>
#include <algorithm>

int maxSumSubarrayOfSizeK(const std::vector<int>& nums, int k) {
    if ((int)nums.size() < k) return 0;

    // Seed the window with the first k elements.
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];
    int best = windowSum;

    // Slide by one each iteration: add entering, subtract leaving.
    for (int i = k; i < (int)nums.size(); i++) {
        windowSum += nums[i] - nums[i - k];
        best = std::max(best, windowSum);
    }
    return best;
}

Watch out:

Initializing best = 0. If all elements are negative, the correct max is negative. Seed best with the initial window sum or -Infinity.
Integer overflow in C++ on large arrays with large values. Use long long when constraints allow n * 10^4 > 2^31.
k > nums.length. Clarify the expected behavior. Returning 0 or throwing an error are both reasonable.

Complexity Analysis

	Time	Space
Brute Force	O(n * k)	O(1)
Optimal (Sliding Window)	O(n)	O(1)

Bottleneck: You must read every element once — O(n) is optimal. No extra structures needed.

Edge Cases

k == n — only one window. Return the sum of the whole array.
k == 1 — return the max element.
All negatives — answer is negative. Make sure best seeds correctly (from the first window, not zero).
k == 0 — clarify. Typically invalid; return 0 or throw.
Single-element array with k = 1 — return that element.

LC 643 — Maximum Average Subarray I — Same window, output mean instead of sum.
LC 239 — Sliding Window Maximum — Window max instead of window sum (uses a monotonic deque).
LC 1456 — Maximum Number of Vowels in a Substring of Given Length — Same pattern with a character-count update.
LC 2090 — K Radius Subarray Averages — Same sliding-sum, different output shape.

OA Strategy Notes

Easy warmup. If this is your problem 1, expect to submit in 5-10 minutes and use the remaining time aggressively on problem 2. Do not overthink: no hash maps, no deques, just a running sum.

What is Expected at Each Level

Junior: Solves in minutes. Identifies sliding window immediately.

Mid-level: Writes the optimal in one pass. Handles edge cases without prompting. Explains why the brute force is O(n * k).

Senior: Mentions overflow, generalizes to variable-size windows (if asked), and references LC 239 as the harder cousin that needs a monotonic deque.

Maximum Sum Subarray of Size K ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Brute Force — Recompute Each Window ​

Optimal — Sliding Window ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

OA Strategy Notes ​

What is Expected at Each Level ​