Maximum Subarray Sum of Size K
Difficulty: Easy
Problem
You are given an array of positive integers and a positive integer k that is at most the length of the array (if k is larger, return 0). Among all runs of exactly k adjacent elements, find the largest total and return it.
Example
Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Of every window of 3 adjacent elements, [5, 1, 3] adds up to the most, giving 9.
Brute-force approach
For each starting position, sum k elements and track the maximum.
Steps
- For each starting index i from 0 to n-k
- Sum k elements starting from i
- Update maxSum if current sum is larger
- Return maxSum
Time complexity: O(n * k) · Space complexity: O(1)
Trade-offs
- Re-sums k elements for every window, adjacent windows share k-1 elements!
- For [2,1,5] → [1,5,1]: we re-added 1 and 5 even though they were already summed
- Can we reuse the previous sum and only add one element and remove one?
Optimal approach
Key insight: When sliding from one window to the next, the sum changes by exactly: +new_right - old_left. No need to re-sum k elements!
Use a fixed-size sliding window: add right element, subtract left element.
Steps
- If the list is shorter than k, return 0
- Sum the first k elements (initial window)
- Set maxSum = initial window sum, and left = 0
- For each right from k to n-1: add nums[right], subtract nums[left], then move left forward
- Update maxSum if windowSum is larger
Time complexity: O(n) · Space complexity: O(1)
Pseudocode
function maxSumSubarrayK(nums, k):
if len(nums) < k: return 0
windowSum = sum(nums[0..k-1])
maxSum = windowSum
left = 0
for right from k to len(nums) - 1:
windowSum += nums[right]
windowSum -= nums[left]
left += 1
maxSum = max(maxSum, windowSum)
return maxSum
Hints
- Think about what changes when the window slides one position right
- Only one element enters and one element leaves
- You don't need to re-sum the entire window each time
Complexity questions
What is the time complexity of the brute force approach?
O(n * k). For each of n-k+1 windows, we sum k elements.
What is the time complexity of the sliding window approach?
O(n). Each element is added once and removed once = O(n).
What is the space complexity for both approaches?
O(1). Only a few variables: windowSum, maxSum, left/right pointers.
Check your understanding of Maximum Subarray Sum of Size K
What does 'contiguous subarray of size k' mean?
k consecutive elements in the array. A contiguous subarray of size k means k elements next to each other.
For [2, 1, 5, 1, 3, 2] with k=3, how many windows of size 3 exist?
4. n - k + 1 = 6 - 3 + 1 = 4 windows: [2,1,5], [1,5,1], [5,1,3], [1,3,2].
For [2, 1, 5, 1, 3, 2] with k=3, what is the maximum sum?
9 (sum of [5, 1, 3]). The four windows are [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6. The maximum is 9.
Related problems
- Longest Substring Without Repeating (Medium)
- Longest Repeating Character Replacement (Medium)
- Permutation in String (Medium)
- Minimum Window Substring (Hard)
- Sliding Window Maximum (Hard)