Find Maximum Sum of Contiguous Subarray Length k

Scenario

Monitoring website traffic and needing the highest traffic within any fixed-length time window.

Question

Given an array of positive integers representing hits per minute and an integer k, return the maximum sum of any contiguous subarray of length k. Provide time and space complexity.

Hints

Two-pointer sliding window keeps running sum; O(n) time, O(1) space.

Max Sum Subarray of Length k

Constraints

• 1 <= n <= 200000 where n = len(nums)
• 1 <= k <= n
• 1 <= nums[i] <= 1000000000
• Result fits in 64-bit signed integer

Examples

Example 1

Input: nums = [2,1,5,1,3,2], k = 3
Output: 9

Explanation: The subarray [5,1,3] has sum 9.

Example 2

Input: nums = [2,3,4,1,5], k = 2
Output: 7

Explanation: The subarray [3,4] has sum 7.

Hints

1. Compute the sum of the first k elements as the initial window.
2. Slide the window by adding the next element and subtracting the element that leaves; track the maximum sum.

Approach

Use a sliding window of size k. Initialize the sum of the first k elements. For each subsequent position, add the entering element and subtract the leaving element to update the running sum in O(1). Keep track of the maximum running sum encountered.

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