Maximum Subarray Sum of Size K

Difficulty: Easy

Problem

You are given an array of positive integers and a positive integer k. 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 just add/remove one element?

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. Sum the first k elements (initial window)
  2. Set maxSum = initial window sum
  3. For each position from k to n-1: slide window
  4. windowSum = windowSum - nums[i-k] + nums[i]
  5. Update maxSum if windowSum is larger

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function maxSumSubarrayK(nums, k):
    maxSum = 0
    windowSum = 0
    start = 0
    
    for end from 0 to len(nums):
        windowSum += nums[end]
        if end >= k - 1:
            maxSum = max(maxSum, windowSum)
            windowSum -= nums[start]
            start += 1
    
    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, start/end 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