Sliding Window

Question 1

325: Maximum Sum Subarray of Size K

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

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

TC - O(n)
SC - O(1)

Answer 1

Takeaways:-
1. Instead of shrinking the window by checking (windowEnd-windowStart+1==k) just slide the window on every iteration if(windowEnd>=k).

Pseudo Code:-
1. Initialize window_start, window_sum and max_sum variables
2. Iterate over given array with index ‘windowEnd’
2.1 Add the current element to the sum
2.2 if windowEnd>=k-1
2.2.1 Assign maximum of max_sum and
window_sum to max_sum.
2.2.2 Subtract the element going out of the
sliding window i.e.,
subtract the window_start index element
of the window from the window_sum.
2.2.3 Increase window_start
3. Return max_sum

Question 2

Smallest Subarray with a given sum

Given an array of positive numbers and a positive number ‘S’, find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0, if no such subarray exists.

Example 1:
Input: [2, 1, 5, 2, 3, 2], S=7

TC - O(n)
SC - O(1)

Answer 2

Takeaways:- Run loop until window_sum>=S and populate the maximum length in the loop itself before shrinking the window.
Pseudo Code:-
1. Initialize window_start, window_sum and min_len variables
2. Iterate over given array with index ‘windowEnd’
2.1 Add the current element to the sum
2.2 while window_sum>=S
2.2.1 Assign minimum length out of min_len and difference of windowEnd and window_start plus one.
2.2.2 Subtract the element going out of the
sliding window i.e.,
subtract the window_start index element
of the window from the window_sum.
2.2.3 Increase window_start
3. Return minLen