How to Use the Sliding-Window Technique to Find the Maximum Sum of a Subarray

Photo by Artturi Jalli on Unsplash

In this article, we are going to solve one of the most asked problems in interviews for big companies.

Sliding Window Technique is one of the most used coding patterns that solve various complex problems in an optimized way by reducing time complexity and space complexity.

Problem Statement

Given an array of positive numbers and a positive number ‘k,’ find the maximum sum of any contiguous subarray of size ‘k’.

Example

Input: [2, 1, 5, 1, 3, 2], k=3 
Output: 9
Explanation: Subarray with maximum sum is [5, 1, 3].

Solution

Algorithm

1. Initially, we take max_sum and window_sum to 0.
2. window_start will be the starting point of the window and window_end is the ending point of the window.
3. First, we calculate the sum of the first subarray of size ‘k’ and add all the elements within the window, and put the value in max_sum.
4. To calculate the sum of the next subarray, we need to slide the window ahead by one element.
5. So to slide the window forward and calculate the sum of the new position of the sliding window.
6. Subtract the element going out of the sliding window, i.e., subtract the first element of the window.
7. Add the new element getting included in the sliding window, i.e., the element coming right after the end of the window.
8. Finally, return the max_sum.

Time Complexity

The Time Complexity of the above algorithm will be O(N).

Space Complexity

Space Complexity is O(1).

And that’s how we do it. Thank you for reading. I hope this helps with your endeavour.

More content at plainenglish.io