What is the brute force approach and complexity for Maximum Sum Subarray of Size K?

Recompute the sum of every block of size k with time complexity O(N · K) and space complexity O(1).

What is the optimal approach and complexity for Maximum Sum Subarray of Size K?

Keep one running window sum; add the new element, drop the old one with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Maximum Sum Subarray of Size K?

Look for key signals in the prompt: "contiguous block" indicates The answer is a range [l … r], not any subset → think window.; "exactly k elements" indicates The window size never changes → Fixed window, no shrinking logic.; "largest sum" indicates Aggregate (sum) that can be updated in O(1) when one element enters and one leaves..

Maximum Sum Subarray of Size K

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelFixed Sliding Window

Complexity:O(N · K)→O(N)

Key Insight

Keep the sum of the current block in one variable. Moving the block one step right changes exactly two elements: one enters on the right, one leaves on the left. So update the sum with one addition and one subtraction.

Core Validity Invariant

The window is valid when it contains exactly k elements. Because we always add one and remove one, it stays valid after the first k elements are loaded — there is no shrinking decision to make.

Problem

You are given an array of integers arr and a number k.

Look at every contiguous block of exactly k elements. Return the largest sum that any such block has.

Input

An integer array arr of length n, and an integer k.

Output

A single number: the maximum sum of any subarray of length exactly k.

Example 1

Input: arr = [100, 200, 300, 400], k = 2

Output: 700

The blocks of size 2 are [100,200]=300, [200,300]=500, [300,400]=700. The largest is 700.

Example 2

Input: arr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4

Output: 39

The block [4, 2, 10, 23] adds up to 39, which is the largest of all size-4 blocks.

Constraints

• 1 ≤ k ≤ n ≤ 10^6
• −10^6 ≤ arr[i] ≤ 10^6
• A sum can exceed the int range — use a 64-bit type.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is the answer about a contiguous block, or can I pick elements from anywhere?
2.
Is the block size fixed or does it change?
3.
If I already know the sum of one block, how does the sum change when I move the block one step to the right?
4.
Which element enters the block, and which element leaves it?
5.
How many blocks of size k are there in total?

Brute force approach

Idea

There are only n − k + 1 blocks of size k. For each one, add up its k elements and keep the largest total.

Thinking process

1
The question asks for a block of exactly k elements, so a block is decided by where it starts.
2
Starts go from 0 to n − k.
3
For each start, loop over the k elements and add them up.
4
Remember the largest sum seen so far.

Visual

Orange cells were already added in the previous window — brute force adds them again.

Brute force repeats workarr = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4step 1/6

arr

▲L

▲R

Work

this window: 4 additions
re-added (already summed before): 0
total additions: 4
sum: 17
best: 17

First window: summed from scratch

Start = 0: add arr[0..3] from scratch → 17.

Code & Implementation

brute.cpp

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr, int k) {
        int n = arr.size();
        long long best = LLONG_MIN;

        // Try every window start.
        for (int start = 0; start + k <= n; start++) {
            long long sum = 0;
            // Re-add all k elements of this window from scratch.
            for (int i = start; i < start + k; i++) {
                sum += arr[i];
            }
            best = max(best, sum);
        }
        return best;
    }
};

class Solution {
    public long maxSubarraySum(int[] arr, int k) {
        int n = arr.length;
        long best = Long.MIN_VALUE;

        // Try every window start.
        for (int start = 0; start + k <= n; start++) {
            long sum = 0;
            // Re-add all k elements of this window from scratch.
            for (int i = start; i < start + k; i++) {
                sum += arr[i];
            }
            best = Math.max(best, sum);
        }
        return best;
    }
}

class Solution:
    def maxSubarraySum(self, arr: list[int], k: int) -> int:
        n = len(arr)
        best = -float("inf")

        # Try every window start.
        for start in range(n - k + 1):
            s = 0
            # Re-add all k elements of this window from scratch.
            for i in range(start, start + k):
                s += arr[i]
            best = max(best, s)

        return int(best)

export function maxSubarraySum(arr: number[], k: number): number {
    const n = arr.length;
    let best = -Infinity;

    // Try every window start.
    for (let start = 0; start + k <= n; start++) {
        let sum = 0;
        // Re-add all k elements of this window from scratch.
        for (let i = start; i < start + k; i++) {
            sum += arr[i];
        }
        best = Math.max(best, sum);
    }
    return best;
}

Complexity

Time O(N · K)Space O(1)

For each of the n − k + 1 starts we do k additions. With n = 10^6 and k = 5·10^5, that is about 2.5·10^11 operations — far too slow.

Better approach

Why brute force is slow

Every block is summed from scratch, even though neighbouring blocks overlap almost completely.

What repeated work are we doing?

The elements in the middle of the array are added up to k times — once for every block that contains them.

What information can we reuse?

Running totals. Once prefix is built, any range sum is prefix[r+1] − prefix[l], so nothing is added twice.

New approach

Idea

Store prefix[i] = sum of the first i elements. Then the block [start … start+k−1] has sum prefix[start+k] − prefix[start], which takes O(1).

Thinking process

1
Brute force adds the same elements again and again for overlapping blocks.
2
If I store the running total up to every index once, any block sum is just the difference of two running totals.
3
Build the prefix array in one pass, then check every start in O(1).

Code & Implementation

better.cpp

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr, int k) {
        int n = arr.size();

        // prefix[i] = sum of the first i elements (arr[0..i-1]).
        vector<long long> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }

        long long best = LLONG_MIN;
        // Window [start .. start+k-1] has sum prefix[start+k] - prefix[start].
        for (int start = 0; start + k <= n; start++) {
            best = max(best, prefix[start + k] - prefix[start]);
        }
        return best;
    }
};

class Solution {
    public long maxSubarraySum(int[] arr, int k) {
        int n = arr.length;

        // prefix[i] = sum of the first i elements (arr[0..i-1]).
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }

        long best = Long.MIN_VALUE;
        // Window [start .. start+k-1] has sum prefix[start+k] - prefix[start].
        for (int start = 0; start + k <= n; start++) {
            best = Math.max(best, prefix[start + k] - prefix[start]);
        }
        return best;
    }
}

class Solution:
    def maxSubarraySum(self, arr: list[int], k: int) -> int:
        n = len(arr)

        # prefix[i] = sum of the first i elements (arr[0..i-1]).
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + arr[i]

        best = -float("inf")
        # Window [start .. start+k-1] has sum prefix[start+k] - prefix[start].
        for start in range(n - k + 1):
            best = max(best, prefix[start + k] - prefix[start])

        return int(best)

export function maxSubarraySum(arr: number[], k: number): number {
    const n = arr.length;

    // prefix[i] = sum of the first i elements (arr[0..i-1]).
    const prefix: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }

    let best = -Infinity;
    // Window [start .. start+k-1] has sum prefix[start+k] - prefix[start].
    for (let start = 0; start + k <= n; start++) {
        best = Math.max(best, prefix[start + k] - prefix[start]);
    }
    return best;
}

Complexity

Time O(N)Space O(N)

Fast enough, but it uses an extra array of size n + 1. We can do the same in O(1) extra space.

Optimized approach

Idea

Start from brute force

Brute force computes the sum of block [i … i+k−1], then throws it away and computes block [i+1 … i+k] from scratch.

Find the repeated work

Those two blocks share k − 1 elements. Brute force adds those shared elements again every single time. Only one element actually changes at each end.

Define the state — what variables do I need?

windowSum: Sum of the elements currently inside the window (always exactly k of them).
right: Index of the element that just entered the window. The window is [right − k + 1 … right].
best: Largest windowSum seen so far.

Define validity

The window is valid when it contains exactly k elements. Because we always add one and remove one, it stays valid after the first k elements are loaded — there is no shrinking decision to make.

Define the transitions — when does each pointer move, and why is it safe?

Every step (right goes from k to n − 1)

windowSum += arr[right]; windowSum -= arr[right − k]

arr[right] is the only new element and arr[right − k] is the only one that fell out. Everything in between is unchanged.

Before the loop

Sum arr[0 … k−1] once

We need one complete window before we can start sliding it.

What does the current window add to the answer?

After each slide, the window is one complete block of size k. Compare its sum with best. Every block is visited exactly once, so the max over all of them is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr, int k) {
        int n = arr.size();
        long long windowSum = 0;

        // 1. Build the first window: arr[0 .. k-1].
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        long long best = windowSum;

        // 2. Slide: add the element entering on the right,
        //    remove the element leaving on the left.
        for (int right = k; right < n; right++) {
            windowSum += arr[right];       // enters
            windowSum -= arr[right - k];   // leaves
            best = max(best, windowSum);
        }
        return best;
    }
};

class Solution {
    public long maxSubarraySum(int[] arr, int k) {
        int n = arr.length;
        long windowSum = 0;

        // 1. Build the first window: arr[0 .. k-1].
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        long best = windowSum;

        // 2. Slide: add the element entering on the right,
        //    remove the element leaving on the left.
        for (int right = k; right < n; right++) {
            windowSum += arr[right];       // enters
            windowSum -= arr[right - k];   // leaves
            best = Math.max(best, windowSum);
        }
        return best;
    }
}

class Solution:
    def maxSubarraySum(self, arr: list[int], k: int) -> int:
        n = len(arr)
        window_sum = 0

        # 1. Build the first window: arr[0 .. k-1].
        for i in range(k):
            window_sum += arr[i]

        best = window_sum

        # 2. Slide: add the element entering on the right,
        #    remove the element leaving on the left.
        for right in range(k, n):
            window_sum += arr[right]       # enters
            window_sum -= arr[right - k]   # leaves
            best = max(best, window_sum)

        return best

export function maxSubarraySum(arr: number[], k: number): number {
    const n = arr.length;
    let windowSum = 0;

    // 1. Build the first window: arr[0 .. k-1].
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    let best = windowSum;

    // 2. Slide: add the element entering on the right,
    //    remove the element leaving on the left.
    for (let right = k; right < n; right++) {
        windowSum += arr[right];       // enters
        windowSum -= arr[right - k];   // leaves
        best = Math.max(best, windowSum);
    }
    return best;
}

Complexity

Time O(N)Space O(1)

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recompute the sum of every block of size k	O(N · K)	O(1)
Better	Precompute running totals; each block sum is one subtraction	O(N)	O(N)
Optimal	Keep one running window sum; add the new element, drop the old one	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous block”The answer is a range [l … r], not any subset → think window.
“exactly k elements”The window size never changes → Fixed window, no shrinking logic.
“largest sum”Aggregate (sum) that can be updated in O(1) when one element enters and one leaves.

Contiguous range+fixed size k+aggregate that can be updated incrementally→Fixed Sliding Window

This is the anchor problem for the whole pattern: it has a window, but no decision about when to shrink. Master the add-right / remove-left move here; every other window problem adds a validity rule on top of it.

Don't make this mistake

Using int for the sum

✗ int windowSum = 0;

✓ long long windowSum = 0;

With up to 10^6 elements of size 10^6, a sum can reach 10^12, which overflows a 32-bit int.

Starting best at 0

✗ long long best = 0;

✓ long long best = sum of the first window;

If every number is negative, the true answer is negative. Starting at 0 would wrongly return 0.

Removing the wrong element

✗ windowSum -= arr[right - k + 1];

✓ windowSum -= arr[right - k];

After adding arr[right], the window must be [right−k+1 … right]. The element that just left is at index right − k. Draw 5 boxes and check it once.

Confusing this with a variable window

There is no "valid / invalid" condition here. If you find yourself writing a while loop to shrink the window, you are solving a different problem. Fixed size → one add, one remove, every step.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Maximum Average Subarray I