Maximum Sum Subarray of Size K — Coding Interview | Sliding Window | 30 Days Preparation Plan | Day 4 — Problem 1

This problem is easy and fun 🥳; hence an appropriate example to introduce the sliding window pattern. The strategy is similar to Smallest Subarray with a Given Sum.

For a better grasp of the problem, after reading each section, try to code that approach. If you get stuck 😉, you can always look at the commented code I have provided for your reference.

This problem is part of the 30 Days Preparation Plan.

Table of Contents

1. Description
2. Brute Force Approach
3. Code
4. Time & Space Complexity
5. Efficient Approach — Sliding Window
6. Code
7. Time & Space Complexity

Description

You have an array of N positive integers and a positive integer K. You have to find the Maximum Sum Subarray of size K.

We will find the maximum sum, but it is easy to print the subarray too. We will see how.

Example 1:
Input:  [4 3 9 5 1 2], K = 3
Output: 17

Explanation: The subarray of size 3 with maximum sum 17 is [3 9 5].

Example 2:
Input:  [1 2 3], K = 2
Output: 5

Explanation: The subarray of size 2 with maximum sum is [2 3].

Let's see the brute force approach now.

Brute Force Approach

The crux of this approach is that we will look at every K sized subarray and choose the subarray with the maximum sum.

Here's the algorithm:

1. Use a loop to iterate through the input array, and for each index, find the sum of the next K elements.
2. Save the highest sum you encounter during the traversal.

The code for this approach is straightforward.

Code

Output:
3 9 5
17

Explanation: The function maximum_sum_subarray_k accepts an array as well as an integer k. It uses a for loop (line 16) that starts from the index 0 until the last index N - K. It uses another nested loop (line 20) to count the sum of the next K elements from the current index.

Line 27 checks if the sum of the current subarray is greater than the maximum sum being maintained so far. If yes, it updates the result (line 29)and saves the resultant subarray's starting index (line 31). The driver function main is used to test the function.

Time & Space Complexity

Time: The time complexity is O(NK), where N is the size of the input array and K is the size of the subarray. The outer loop runs for N times, and the nested inner loop runs K times.

Space: Since this approach does not need extra space, space complexity is O(1).

Efficient Approach — Sliding window

Before explaining how the sliding window works, look at this animation, which shows the sum of each window of size 3.

Notice that the sum of each window is calculated using the sum of the previous window and applying these two operations.

1. When the window is sliding, one element goes out of the window. Hence we subtract that element from the sum.
2. The next element becomes part of the window. Hence we add that element to the sum.

This algorithm needs only a single iteration of the array, making it linear 🥳. Unlike the brute force approach, we are not repeatedly calculating the sum of subarrays that already have been computed but using only two constant operations (addition and subtraction).

Now, let's see the fun part.

Code

Output:
17

Explanation: On lines 12 to 15, we compute the sum of the first K elements of the array so that we can use it to calculate the sum of the next subarray. Another loop traverses the array from index k to the end (line 19).

On line 22, we add the kth element (that becomes part of the sliding windows) and subtract the (i - k)th element (the first element of the previous subarray). Finally, we update the result if the current subarray sum is greater than our maximum sum so far.

Time & Space Complexity

Time: Since we are only doing a single array iteration, the time complexity is O(n).

Space: We are not using any extra space; hence space complexity is constant.

If you like this article, please give it a clap 👏.