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

  1. For each starting index i from 0 to n-k
  2. Sum k elements starting from i
  3. Update maxSum if current sum is larger
  4. 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

  1. If the list is shorter than k, return 0
  2. Sum the first k elements (initial window)
  3. Set maxSum = initial window sum, and left = 0
  4. For each right from k to n-1: add nums[right], subtract nums[left], then move left forward
  5. 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

Keep practising