Last Updated: 12 Nov, 2020
Minimum Sum Subarray Of Given Size
Easy
Asked in companies
You have been given an array 'ARR' of integers consisting of ‘N’ integers and a positive integer ‘K’. Your task is to find a subarray(contiguous) of size ‘K’ such that the sum of its elements is minimum.
Note :
You can assume that the value of ‘K’ will always be less than or equal to ‘N’. So, the answer will always exist.
Input Format :
The first line of input contains two single space-separated integers ‘N’ and ‘K’ representing the size of the array and the given integer, respectively.
The second line of input contains 'N' single space-separated integers representing the array elements.
Output Format :
Print the minimum possible subarray sum.
Print the output of each test case in a new line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= N <= 10^5
1 <= K <= N
-10^5 <= ARR[i] <= 10^5
Time Limit: 1sec
Approaches
We have a simple brute force solution for this problem. We will traverse over all subarrays of size ‘K’ and calculate their sum. Finally, we return the minimum of all subarray sums.
We can naively find all subarrays of size ‘K’ by two nested loops. The outer loop (running from 0 to N - K) will iterate over the starting index of all the subarrays, and the inner loop (running from i to i + K) will be used to calculate the sum of elements of the current subarray of size ‘K’.
A sliding window of size ‘K’ can be maintained while traversing the array left to right. Using this, we can easily compute the sum of all subarrays (other than the first subarray) of size ‘K’ by removing the first element of the previous window/subarray and adding the current element to the window.
Algorithm
- We store the sum of the first window/subarray of size ‘K’ in ‘minSum’.
- We initialize ‘currWindowSum’ to ‘minSum’.
- We now traverse the rest of the array.
- We compute ‘currWindowSum’ by removing the leftmost element i.e. ARR[i-K] and including the current element i.e. ARR[i].
- We set ‘minSum’ to the minimum of ‘minSum’ and ‘currWindowSum’.
- Finally, we return ‘minSum’ as result.
Similar problems