Maximum Subarray of Size K
Understand the problem
You are given an integer array nums and an integer k. Find the largest sum of a contiguous subarray of exactly k elements.
Examples:
nums = [2, 1, 5, 1, 3, 2], k = 3
output = 9 // subarray [5, 1, 3] has sum 5+1+3 = 9
nums = [2, 3, 4, 1, 5], k = 2
output = 7 // subarray [3, 4] has sum 3+4 = 7This is the introductory problem for the Sliding Window technique — a fixed-size window moves from left to right.
Show the basic approach (slower)
O(n·k) time, O(1) spacefunction maxSubarrayOfSizeK(nums: number[], k: number): number {
let maxSum = -Infinity
for (let i = 0; i <= nums.length - k; i++) {
let windowSum = 0
for (let j = i; j < i + k; j++) {
windowSum += nums[j]
}
maxSum = Math.max(maxSum, windowSum)
}
return maxSum
}For each starting position, add up k elements from scratch.
- When k is large (close to n) this approaches O(n²).
- A sliding window removes this redundant work.
Optimal solution
O(n) time, O(1) spacefunction maxSubarrayOfSizeK(nums: number[], k: number): number {
let windowSum = 0
let maxSum = -Infinity
let left = 0
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right] // expand the window to the right
if (right >= k - 1) { // window has k elements
maxSum = Math.max(maxSum, windowSum)
windowSum -= nums[left] // shrink from the left
left++
}
}
return maxSum
}The optimal approach uses a fixed-size Sliding Window of size k: each step adds the new element on the right and subtracts the old element on the left.
There is no re-summing from scratch, and each element is processed exactly once.
Step-by-step trace
1function maxSubarrayOfSizeK(nums: number[], k: number): number {2 let windowSum = 03 let maxSum = -Infinity4 let left = 05 for (let right = 0; right < nums.length; right++) {6 windowSum += nums[right] // expand the window to the right7 if (right >= k - 1) { // window has k elements8 maxSum = Math.max(maxSum, windowSum)9 windowSum -= nums[left] // shrink from the left10 left++11 }12 }13 return maxSum14}Edge cases to remember
k equals the array length — the whole array is a single window, return the total sum.
k=1 — return the largest element in the array.
All elements negative — still correct because maxSum starts at -Infinity.
k larger than the array length — the condition if (right >= k-1) is never true, so maxSum is never updated (returns -Infinity); validate k ≤ n first.