Compile Ready
Module 2 · Fixed Window

Maximum Sum Subarray of Size K

EasyProblem 2 of 17 7 min read ~13 min to solve
Sliding WindowFixed WindowArrayRunning Sum
Asked atAmazonGoogleMicrosoftAdobeOracle

Problem Statement

Given an integer array nums and an integer k, return the maximum sum of any contiguous subarray whose length is exactly k.

Input

An integer array nums and an integer k, the exact number of elements each candidate subarray must contain.

Output

An integer: the largest sum among all contiguous subarrays of length k.

Constraints

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

Examples

Example 1

Input: 
nums = [2,1,5,1,3,2], k = 3
Output: 9
Explanation: The best length-3 window is **[5,1,3]**, whose sum is **9**.

Example 2

Input: 
nums = [2,3,4,1,5], k = 2
Output: 7
Explanation: The maximum length-2 sum is from **[3,4]**, which totals **7**.

Example 3

Input: 
nums = [-3,-2,-5,-1], k = 2
Output: -5
Explanation: The best window is **[-3,-2]**. Initialising from the first window is necessary because every sum is negative.

Learning Objectives

  • Identify a fixed-size window when the subarray length is exactly **k**.
  • Maintain a running sum instead of recomputing each candidate window.
  • Update the window in the correct add-entering, remove-leaving sequence.
  • Correctly handle arrays containing negative values.

Intuition

The phrase contiguous subarray of length exactly k tells you every candidate covers a fixed number of neighbouring elements. If the window starting at index 0 is known, the window starting at index 1 is almost the same: it drops nums[0] and gains nums[k].

The wasteful idea is to loop over every start index and sum the next k values again. That turns overlapping work into repeated work. A fixed sliding window keeps the overlapping part of the sum and only updates the two values that changed.

Common mistakes

  • ×Using Kadane's algorithm, which finds any-length subarrays instead of exactly length **k**.
  • ×Starting **bestSum** at **0**, which is wrong when the maximum valid sum is negative.
  • ×Updating the best answer before the window has reached size **k**.
  • ×Subtracting **nums[right - k + 1]** instead of the element that actually left the window.

Algorithm Explanation

Window setup

Keep windowSum for the current length-k window and bestSum for the largest complete window sum seen so far. The window is valid only after it contains exactly k elements.

Window visualization

For nums = [2,1,5,1,3,2] and k = 3, the first window [2,1,5] has sum 8. Slide right: 2 leaves, 1 enters, and [1,5,1] has sum 7. Slide again: 1 leaves, 3 enters, and [5,1,3] has sum 9. The final slide removes 5, adds 2, and gives [1,3,2] with sum 6. The best sum is 9.

Algorithm

  1. Add the first k elements to create the first complete window.
  2. Initialise bestSum with that first window sum.
  3. Move the right edge from index k to the end.
  4. Add the entering value at right.
  5. Remove the leaving value at right - k.
  6. Update bestSum with the larger of the current best and current window sum.
  7. Return bestSum.

Solutions

Solution: Fixed-size running sum

The optimal solution is the fixed-window template. Build the first length-k sum once, then slide the window across the array in O(1) time per position.

Step-by-step

  1. Sum the first k elements.
  2. Save that sum as bestSum so negative-only inputs are handled correctly.
  3. For every later index, add the entering value on the right.
  4. Subtract the value exactly k positions behind the right edge.
  5. Keep the maximum complete-window sum and return it.
Time

O(n)

Space

O(1)

The scan performs constant work for each array element.

Java implementation

Loading…

Dry Run

Sample input

nums = [2,1,5,1,3,2], k = 3. Trace each complete window and the best sum seen so far.

stepentering valueleaving valuewindow sumbest sum
initial window [2,1,5]2, 1, 5none88
right = 31278
right = 43199
right = 52569

The maximum complete-window sum is 9, produced by the subarray [5,1,3].

Interview Tips

Distinguish this from maximum subarray immediately. Kadane's algorithm optimises over any length, while this problem fixes the length at k. The interviewer wants to hear that each slide preserves k - 1 old elements and changes only the entering and leaving values.

Likely follow-ups

  • How would you also return the subarray boundaries for the best window?
  • How would you find the minimum sum subarray of size **k**?
  • What changes if the required window size can vary between **1** and **k**?
  • How would you answer many fixed-window sum queries on the same array?

Similar Problems

Maximum Average Subarray I
EasyUses the identical window sum and divides the final best sum by k.
Contains Duplicate II
EasyAnother fixed-width window, but the state is a set instead of a sum.
Sliding Window Maximum
HardFixed window with a monotonic deque for max queries.
Subarray Product Less Than K
MediumA variable-window product problem where feasibility changes with window size.

Key Takeaways

  • Exactly length **k** means every candidate can be generated by sliding one position.
  • The running sum changes by adding the entering value and subtracting the leaving value.
  • Use the first full window as the initial best answer.
  • Do not use any-length subarray algorithms when the length is fixed.
Reusable template: For an exact-size-k aggregate, compute the first window once, slide by one element at a time, update the aggregate in constant time, and record the best complete window.