Maximum Sum Subarray of Size K

Q: What is a fixed size sliding window?

It is a range of exactly k neighbouring elements that moves one step at a time across an array. Instead of recomputing the range from scratch at each position, you update a running value: add the element that enters on the right and remove the one that leaves on the left. That turns O(n·k) work into O(n) .

Q: What is the time complexity of the maximum sum subarray of size k?

With a sliding window it is O(n) time and O(1) extra space: one pass to sum the first window, then one addition and one subtraction per step. Adding up every window separately costs (n-k+1) × k additions, which is O(n·k) , about 2.5 × 10^7 for n = 10^4 and k = 5000 .

Q: How is this different from the maximum subarray problem?

Here the length is fixed at k , so every candidate is a window and a sliding sum covers them all. In the maximum subarray problem the length is free, and you need Kadane's algorithm, which decides at each element whether to extend the current run or start a new one. A fixed window never has that choice.

Q: Can prefix sums solve it too?

Yes. Build prefix[i] as the sum of the first i elements, and the window starting at s sums to prefix[s+k] - prefix[s] . That is also O(n) time, but it stores n+1 totals. The sliding window gets the same sums with two variables.

EasySliding window

+10

You get an array of integers nums and a window length k. Look at every run of exactly k neighbouring elements and return the largest sum among them. The values can be negative, so the answer can be negative too.

Function

maxSumSubarray(nums: integer-array, k: integer) → integer

numsinteger-array: the array of integers
kinteger: how many neighbouring elements each window holds
Returnsinteger: the largest sum of any k consecutive elements

Constraints

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴

Examples

Input: nums = [4, -1, 3, 7, -2, 5, 1]k = 3
Output: 10
Explanation: The five windows of length 3 add up to 6, 9, 8, 10 and 4. The largest is 7 + (-2) + 5 = 10.

Input: nums = [-3, -8, -1, -6]k = 2
Output: -7
Explanation: Every value is negative, so every window sum is too: -11, -9 and -7. The largest of them is -1 + (-6) = -7.

Input: nums = [5, -2, 4]k = 3
Output: 7
Explanation: When k equals the length of the array there is one window, the whole array, and 5 + (-2) + 4 = 7.

+15 hidden tests on Submit

Follow-up

Can you also return where the best window starts, picking the leftmost one when several windows tie?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

There are n-k+1 windows, and adding each one up from scratch costs k additions. The trick is that two neighbouring windows overlap in all but two elements. Slide the window instead of rebuilding it: one value enters, one value leaves, and every window sum costs two operations.

Add up every window

Correct, but does not finish on the largest tests

Intuition

A window is fixed by where it starts. It can start at index 0, 1, and so on up to n-k, because a later start would run past the end of the array. For each start, add the k elements and compare the total with the best so far.

For [4, -1, 3, 7, -2, 5, 1] and k = 3 that gives the sums 6, 9, 8, 10, 4, and the answer is 10. Start the best at the first window's sum, or at the smallest integer, never at 0: with all values negative, 0 would beat every real window.

The cost is (n-k+1) × k additions. It peaks when k is about half of n: with n = 10^4 and k = 5000 that is 5001 × 5000, about 2.5 × 10^7 additions, and almost all of them repeat work done for the window before.

Algorithm

Set best to the smallest possible value.
For each start from 0 to n-k, set total = 0.
Add nums[start] through nums[start+k-1] to total.
If total beats best, store it.
Return best.

def maxSumSubarray(nums, k):
    n = len(nums)
    best = None
    for start in range(n - k + 1):
        total = 0
        for i in range(start, start + k):
            total += nums[i]
        if best is None or total > best:
            best = total
    return best

Slide a fixed window

Intuition

Compare the window starting at index 0 with the one starting at index 1. In [4, -1, 3, 7, -2, 5, 1] with k = 3, they are 4 + (-1) + 3 = 6 and (-1) + 3 + 7 = 9. Both contain -1 and 3. The second sum is the first one plus the value that entered, 7, minus the value that left, 4: 6 + 7 - 4 = 9.

That holds for every step. When the window's right end moves to index i, the element at i enters and the element at i-k leaves. So you add up the first window once, then update the sum with one addition and one subtraction per step. The sums go 6, 9, 8, 10, 4, the same as the brute force, and you keep the largest.

Each element enters once and leaves at most once, so the time is O(n). You keep two numbers, the current window sum and the best one, so the extra space is O(1). No sum here passes 10^4 × 10^4 = 10^8 in size, so a 32-bit integer is enough.

Algorithm

Add up nums[0] through nums[k-1] into window.
Set best = window.
For every i from k to n-1, add nums[i] and subtract nums[i-k].
After each step, set best to the larger of best and window.
Return best.

def maxSumSubarray(nums, k):
    # Sum of the first window, nums[0..k-1].
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        # Slide one step right: nums[i] enters, nums[i-k] leaves.
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Pitfalls and edge cases

The window idea is short, so the bugs hide in the starting values and the indexes.

Starting best at 0. With [-3, -8, -1, -6] and k = 2 the real answer is -7, but a best of 0 is never beaten and comes back as the answer.
Subtracting the wrong element. When nums[i] enters, the one that leaves is nums[i-k]. Using nums[i-k+1] or nums[i-k-1] gives windows of the wrong length.
Stopping the brute force one start too early. The last window starts at n-k, so the loop must include it. With k = n that is the only window, and an off-by-one checks no window and returns the starting value of best.
Comparing only after the loop. The best window can be the first one, so compare the first sum too, or initialise best with it.
Forgetting that R and Lua count from 1. The first window is nums[1..k], and the element that leaves when nums[i] enters is still nums[i-k].

Frequently asked questions4

What is a fixed size sliding window?

It is a range of exactly k neighbouring elements that moves one step at a time across an array. Instead of recomputing the range from scratch at each position, you update a running value: add the element that enters on the right and remove the one that leaves on the left. That turns O(n·k) work into O(n).

What is the time complexity of the maximum sum subarray of size k?

With a sliding window it is O(n) time and O(1) extra space: one pass to sum the first window, then one addition and one subtraction per step. Adding up every window separately costs (n-k+1) × k additions, which is O(n·k), about 2.5 × 10^7 for n = 10^4 and k = 5000.

How is this different from the maximum subarray problem?

Here the length is fixed at k, so every candidate is a window and a sliding sum covers them all. In the maximum subarray problem the length is free, and you need Kadane's algorithm, which decides at each element whether to extend the current run or start a new one. A fixed window never has that choice.

Can prefix sums solve it too?

Yes. Build prefix[i] as the sum of the first i elements, and the window starting at s sums to prefix[s+k] - prefix[s]. That is also O(n) time, but it stores n+1 totals. The sliding window gets the same sums with two variables.

Python

def maxSumSubarray(nums, k):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [4, -1, 3, 7, -2, 5, 1]
k = 3

Expected