Maximum Sum Subarray of Size K

🎯

Maximum Sum Subarray of Size K

easySLIDING_WINDOWAmazonGoogle

Imagine you are analyzing daily sales data and want to find the period of K consecutive days with the highest total sales to plan promotions effectively.

💡 This problem is a classic example of using a fixed-size sliding window to efficiently compute sums over subarrays. Beginners often struggle because they try to recompute sums from scratch for every subarray, leading to inefficient solutions.

📋

Problem Statement

Given an array of integers and an integer K, find the maximum sum of any contiguous subarray of size K.

1 ≤ n ≤ 10^51 ≤ K ≤ n-10^4 ≤ array elements ≤ 10^4

💡

Example

Input"arr = [2, 1, 5, 1, 3, 2], K = 3"

Output9

The subarray [5, 1, 3] has the maximum sum 9.

Input"arr = [2, 3, 4, 1, 5], K = 2"

Output7

The subarray [3, 4] has the maximum sum 7.

• K equals array length → sum of entire array
• All negative numbers → maximum sum is the least negative sum of size K
• K is 1 → maximum element in the array
• Array contains zeros → subarray sum might be zero

⚠️

Common Mistakes

Recomputing sum for every subarray instead of sliding window update

Leads to time limit exceeded on large inputs

✅ Use sliding window to update sum in O(1) time per step

Not handling edge case when K equals array length

May cause index errors or incorrect results

✅ Ensure loops and indices handle K = n correctly

Forgetting to initialize max_sum properly (e.g., zero instead of -inf)

Incorrect max sum if all numbers are negative

✅ Initialize max_sum to negative infinity or first window sum

Off-by-one errors in loop boundaries

Array index out of bounds or missing subarrays

✅ Carefully set loop ranges from 0 to n-k inclusive

Not checking if K is valid (e.g., K > n)

Runtime errors or incorrect results

✅ Validate input constraints before processing

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly computing sums of all possible subarrays of size K, which helps understand the problem before optimizing.

Intuition

Check every possible subarray of size K by summing its elements and track the maximum sum found.

Algorithm

1. Initialize max_sum to smallest possible integer.
2. For each index i from 0 to n-K:
3. Calculate the sum of subarray from i to i+K-1.
4. Update max_sum if current sum is greater.

💡 The nested loops make it clear how we consider every subarray, but summing repeatedly is inefficient.

</>

Code

def max_sum_subarray_brute(arr, k):
    n = len(arr)
    max_sum = float('-inf')
    for i in range(n - k + 1):
        current_sum = 0
        for j in range(i, i + k):
            current_sum += arr[j]
        if current_sum > max_sum:
            max_sum = current_sum
    return max_sum

# Driver code
if __name__ == '__main__':
    arr = [2, 1, 5, 1, 3, 2]
    k = 3
    print(max_sum_subarray_brute(arr, k))  # Output: 9

Line Notes

n = len(arr)Determine the length of the array to set loop boundaries

max_sum = float('-inf')Initialize max_sum to smallest number to ensure any sum will be larger

for i in range(n - k + 1)Loop over all valid starting indices for subarrays of size k

for j in range(i, i + k)Sum elements in the current subarray from i to i+k-1

public class MaxSumSubarrayBrute {
    public static int maxSumSubarrayBrute(int[] arr, int k) {
        int n = arr.length;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            for (int j = i; j < i + k; j++) {
                currentSum += arr[j];
            }
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println(maxSumSubarrayBrute(arr, k)); // Output: 9
    }
}

Line Notes

int n = arr.length;Get array length for loop limits

int maxSum = Integer.MIN_VALUE;Initialize maxSum to smallest integer to track maximum

for (int i = 0; i <= n - k; i++)Iterate over all starting indices for subarrays of size k

for (int j = i; j < i + k; j++)Sum elements in the current subarray

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSumSubarrayBrute(const vector<int>& arr, int k) {
    int n = arr.size();
    int maxSum = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int currentSum = 0;
        for (int j = i; j < i + k; j++) {
            currentSum += arr[j];
        }
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return maxSum;
}

int main() {
    vector<int> arr = {2, 1, 5, 1, 3, 2};
    int k = 3;
    cout << maxSumSubarrayBrute(arr, k) << endl; // Output: 9
    return 0;
}

Line Notes

int n = arr.size();Get size of vector for loop boundaries

int maxSum = INT_MIN;Initialize maxSum to smallest int to track maximum sum

for (int i = 0; i <= n - k; i++)Loop over all valid start indices for subarrays

for (int j = i; j < i + k; j++)Sum elements in the current subarray

function maxSumSubarrayBrute(arr, k) {
    const n = arr.length;
    let maxSum = -Infinity;
    for (let i = 0; i <= n - k; i++) {
        let currentSum = 0;
        for (let j = i; j < i + k; j++) {
            currentSum += arr[j];
        }
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }
    return maxSum;
}

// Test
const arr = [2, 1, 5, 1, 3, 2];
const k = 3;
console.log(maxSumSubarrayBrute(arr, k)); // Output: 9

Line Notes

const n = arr.length;Store array length for loop limits

let maxSum = -Infinity;Initialize maxSum to smallest number to track maximum

for (let i = 0; i <= n - k; i++)Iterate over all possible subarray start indices

for (let j = i; j < i + k; j++)Sum elements in the current subarray

⏱

Complexity

TimeO(n*k)

SpaceO(1)

For each of the n-k+1 subarrays, we sum k elements, resulting in O(n*k) time.

💡 If n=1000 and k=500, this means about 500,000 operations, which is inefficient for large inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for large arrays, so we need to optimize it using a better technique.

🧠

Sliding Window (Optimal)

💡 This approach improves efficiency by reusing the sum from the previous window instead of recomputing it, demonstrating the power of the sliding window technique.

Intuition

Calculate the sum of the first window of size K, then slide the window by one element at a time, updating the sum by subtracting the element leaving and adding the new element entering.

Algorithm

1. Calculate the sum of the first K elements.
2. Initialize max_sum with this initial sum.
3. For each index i from K to n-1:
4. Update current sum by subtracting arr[i-K] and adding arr[i].
5. Update max_sum if current sum is greater.

💡 This approach avoids repeated summation by maintaining a running sum, making it much faster.

</>

Code

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

# Driver code
if __name__ == '__main__':
    arr = [2, 1, 5, 1, 3, 2]
    k = 3
    print(max_sum_subarray_sliding_window(arr, k))  # Output: 9

Line Notes

window_sum = sum(arr[:k])Initialize sum with first window of size k

max_sum = window_sumSet max_sum to initial window sum

for i in range(k, n)Slide window from index k to end

window_sum += arr[i] - arr[i - k]Update sum by adding new element and removing old

public class MaxSumSubarraySlidingWindow {
    public static int maxSumSubarraySlidingWindow(int[] arr, int k) {
        int n = arr.length;
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        int maxSum = windowSum;
        for (int i = k; i < n; i++) {
            windowSum += arr[i] - arr[i - k];
            if (windowSum > maxSum) {
                maxSum = windowSum;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 3;
        System.out.println(maxSumSubarraySlidingWindow(arr, k)); // Output: 9
    }
}

Line Notes

int windowSum = 0;Initialize sum for the first window

for (int i = 0; i < k; i++)Sum first k elements to form initial window

for (int i = k; i < n; i++)Slide window through array

windowSum += arr[i] - arr[i - k];Update sum by adding new and removing old element

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSumSubarraySlidingWindow(const vector<int>& arr, int k) {
    int n = arr.size();
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    int maxSum = windowSum;
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }
    return maxSum;
}

int main() {
    vector<int> arr = {2, 1, 5, 1, 3, 2};
    int k = 3;
    cout << maxSumSubarraySlidingWindow(arr, k) << endl; // Output: 9
    return 0;
}

Line Notes

int windowSum = 0;Initialize sum for first window

for (int i = 0; i < k; i++)Sum first k elements to start

for (int i = k; i < n; i++)Slide window across array

windowSum += arr[i] - arr[i - k];Adjust sum by removing left and adding right element

function maxSumSubarraySlidingWindow(arr, k) {
    const n = arr.length;
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    let maxSum = windowSum;
    for (let i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }
    return maxSum;
}

// Test
const arr = [2, 1, 5, 1, 3, 2];
const k = 3;
console.log(maxSumSubarraySlidingWindow(arr, k)); // Output: 9

Line Notes

let windowSum = 0;Initialize sum for first window

for (let i = 0; i < k; i++)Sum first k elements to form initial window

for (let i = k; i < n; i++)Slide window through array

windowSum += arr[i] - arr[i - k];Update sum by adding new and removing old element

⏱

Complexity

TimeO(n)

SpaceO(1)

We compute the sum of the first window once, then update the sum in constant time for each of the remaining n-k windows.

💡 For n=1000, this means roughly 1000 operations, which is efficient for large inputs.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews.

🧠

Sliding Window with Early Exit for K=1

💡 This approach handles the special case when K=1 by simply returning the maximum element, which is a useful optimization and edge case handling.

Intuition

If the window size is 1, the maximum sum subarray is the maximum element itself, so we can return it immediately without sliding.

Algorithm

1. If K equals 1, return the maximum element in the array.
2. Otherwise, use the sliding window approach to find the maximum sum subarray.

💡 This approach combines a quick shortcut for a special case with the optimal sliding window method.

</>

Code

def max_sum_subarray_k1_optimized(arr, k):
    if k == 1:
        return max(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

# Driver code
if __name__ == '__main__':
    arr = [2, 1, 5, 1, 3, 2]
    k = 1
    print(max_sum_subarray_k1_optimized(arr, k))  # Output: 5

Line Notes

if k == 1:Check for special case where window size is 1

return max(arr)Return maximum element directly for k=1

window_sum = sum(arr[:k])Initialize sum for first window when k>1

for i in range(k, len(arr))Slide window and update sums for k>1

public class MaxSumSubarrayK1Optimized {
    public static int maxSumSubarrayK1Optimized(int[] arr, int k) {
        if (k == 1) {
            int maxVal = Integer.MIN_VALUE;
            for (int val : arr) {
                if (val > maxVal) maxVal = val;
            }
            return maxVal;
        }
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        int maxSum = windowSum;
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            if (windowSum > maxSum) {
                maxSum = windowSum;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {2, 1, 5, 1, 3, 2};
        int k = 1;
        System.out.println(maxSumSubarrayK1Optimized(arr, k)); // Output: 5
    }
}

Line Notes

if (k == 1)Check if window size is 1 for shortcut

for (int val : arr)Find maximum element when k=1

for (int i = 0; i < k; i++)Sum first k elements for sliding window

for (int i = k; i < arr.length; i++)Slide window and update sums

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSumSubarrayK1Optimized(const vector<int>& arr, int k) {
    if (k == 1) {
        int maxVal = INT_MIN;
        for (int val : arr) {
            if (val > maxVal) maxVal = val;
        }
        return maxVal;
    }
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    int maxSum = windowSum;
    for (int i = k; i < (int)arr.size(); i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }
    return maxSum;
}

int main() {
    vector<int> arr = {2, 1, 5, 1, 3, 2};
    int k = 1;
    cout << maxSumSubarrayK1Optimized(arr, k) << endl; // Output: 5
    return 0;
}

Line Notes

if (k == 1)Check for special case where window size is 1

for (int val : arr)Find maximum element in array for k=1

for (int i = 0; i < k; i++)Sum first k elements for sliding window

for (int i = k; i < (int)arr.size(); i++)Slide window and update sums

function maxSumSubarrayK1Optimized(arr, k) {
    if (k === 1) {
        return Math.max(...arr);
    }
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    let maxSum = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }
    return maxSum;
}

// Test
const arr = [2, 1, 5, 1, 3, 2];
const k = 1;
console.log(maxSumSubarrayK1Optimized(arr, k)); // Output: 5

Line Notes

if (k === 1)Check for window size 1 special case

return Math.max(...arr);Return max element directly for k=1

for (let i = 0; i < k; i++)Sum first k elements for sliding window

for (let i = k; i < arr.length; i++)Slide window and update sums

⏱

Complexity

TimeO(n)

SpaceO(1)

Finding max element for k=1 is O(n), sliding window for k>1 is O(n).

💡 This optimization saves time for the special case without affecting general performance.

Interview Verdict: Accepted

This approach is optimal and handles edge cases gracefully, showing thoroughness.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the sliding window approach is best for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*k)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window	O(n)	O(1)	No	Yes (can track indices)	Code this approach for optimal solution
3. Sliding Window with K=1 Optimization	O(n)	O(1)	No	Yes	Mention as edge case optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the sliding window technique as an optimization.Step 4: Mention edge cases and possible optimizations like handling K=1.Step 5: Code the sliding window solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to identify the sliding window pattern, optimize from brute force, handle edge cases, and write clean code.

Common Follow-ups

• What if the array contains negative numbers? → Sliding window still works.
• Can you find the subarray itself, not just the sum? → Track start index during sliding.

💡 These follow-ups test your understanding of the pattern's flexibility and your ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Asked for max/min sum or average of subarrays, 2) Fixed size K given, 3) Need contiguous elements, 4) Optimize from naive O(n*k) to O(n).

Signature Phrases

maximum sum subarray of size Kcontiguous subarrayfixed window size

NOT This Pattern When

Problems asking for subsequences or non-contiguous elements are not sliding window problems.

Similar Problems

Maximum Average Subarray I - similar sliding window sum with average calculationMinimum Size Subarray Sum - variable size sliding window patternSliding Window Maximum - sliding window with max instead of sum

Practice

1. Consider the following Python code implementing the optimal sliding window solution for the fruits problem. What is the returned value when the input is [1, 2, 1]?

def totalFruit(fruits):
    basket = {}
    left = 0
    max_length = 0
    for right in range(len(fruits)):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace iterations for input [1, 2, 1]

   Right=0: basket={1:1}, max_length=1; Right=1: basket={1:1,2:1}, max_length=2; Right=2: basket={1:2,2:1}, max_length=3.

2. Step 2: No window shrinking needed as basket size never exceeds 2

   Final max_length is 3, the length of entire array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All fruits fit in one window of length 3 [OK]

Hint: Count window length when basket size ≤ 2 [OK]

Common Mistakes:

• Off-by-one in window length
• Shrinking window unnecessarily
• Miscounting basket size

2. You need to find the length of the longest substring in a string that contains at most k distinct characters. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with a frequency map or ordered dictionary to dynamically track distinct characters

B. Brute force checking of all substrings and counting distinct characters each time

C. Dynamic programming with a 2D table storing substring states

D. Greedy approach that expands the substring until distinct characters exceed k, then resets

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest substring with at most k distinct characters, which suggests a variable-size window approach.

2. Step 2: Identify optimal approach

   Sliding window with a frequency map or ordered dictionary efficiently tracks distinct characters and adjusts window size in O(n) time, unlike brute force or DP.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with frequency map is standard for this problem [OK]

Hint: Sliding window with frequency map solves this in O(n) [OK]

Common Mistakes:

• Thinking brute force or DP is efficient enough
• Assuming greedy reset works without shrinking window properly

3. You are given a binary array and an integer k. You want to find the length of the longest contiguous subarray containing only 1s after flipping at most k zeros to 1s. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with two pointers maintaining a window that contains at most k zeros

B. Brute force nested loops checking all subarrays and counting zeros each time

C. Dynamic programming with memoization over subarray indices and zero counts

D. Greedy approach flipping zeros as soon as encountered without shrinking window

Solution

1. Step 1: Understand problem constraints

   The problem requires the longest subarray with at most k zeros flipped to ones, which suggests a variable-size window approach.

2. Step 2: Identify suitable algorithm

   Sliding window with two pointers efficiently tracks the window boundaries and zero count, allowing linear time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with two pointers is the classic optimal approach for this problem [OK]

Hint: Longest subarray with constraints -> sliding window [OK]

Common Mistakes:

• Assuming greedy flipping without window shrink works
• Using DP unnecessarily
• Brute force is too slow

4. Consider the following Python function implementing the sliding window approach to find the minimum size subarray sum. What is the returned value when calling min_subarray_len(5, [1,2,3,4])?

def min_subarray_len(target, nums):
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')
    for right in range(n):
        current_sum += nums[right]
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if min_length == float('inf') else min_length

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace iterations and sums

   Right=0: sum=1 (less than 5), Right=1: sum=3 (less than 5), Right=2: sum=6 (≥5), update min_length=3, shrink window: sum=6-1=5, left=1, update min_length=2, shrink again: sum=5-2=3 (less than 5), stop shrinking.

2. Step 2: Continue to Right=3

   sum=3+4=7 (≥5), update min_length=min(2,3)=2, shrink: sum=7-3=4 (less than 5), stop shrinking.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimal subarray length with sum≥5 is 2 ([2,3] or [4]) [OK]

Hint: Shrink window while sum ≥ target to find minimal length [OK]

Common Mistakes:

• Off-by-one in window length calculation
• Not shrinking window properly
• Returning min_length without checking infinity

5. The following code attempts to find the maximum average subarray of size k using a sliding window. Identify the line containing the subtle bug that could cause incorrect results or runtime errors.

medium

A. Line 3: initializing current_sum with sum of first k elements

B. Line 6: updating current_sum by adding nums[i] and nums[i - k]

C. Line 5: loop range starting from k to n

D. Line 8: updating max_sum if current_sum is greater

Solution

1. Step 1: Examine update to current_sum

   The line adds nums[i] and nums[i - k], but it should add nums[i] and subtract nums[i - k] to slide the window correctly.

2. Step 2: Identify impact of bug

   Adding both elements inflates current_sum incorrectly, leading to wrong maximum average or runtime errors if indices go out of range.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window requires subtracting the element leaving the window [OK]

Hint: Sliding window sum updates by adding new and subtracting old element [OK]

Common Mistakes:

• Using addition instead of subtraction in window update
• Off-by-one errors in loop boundaries