Minimum Sum Subarray Of Given Size

Easy

0/40

Average time to solve is 15m

Contributed by

331 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

8 3
10 4 2 5 6 3 8 1

Sample Output 1 :

Explanation Of Sample Input

All subarrays of size 3 and their respective sums are-
{10, 4, 1} : sum → 10+4+1 = 15
{4, 2, 5} : sum → 4+2+5 = 11
{2, 5, 6} : sum → 2+5+6 = 13
{5, 6, 3} : sum → 5+6+3 = 14
{6, 3, 8} : sum → 6+3+8 = 17
{3, 8, 1} : sum → 3+8+1 = 12

The subarray with a minimum sum of 11 is {4, 2, 5}.

Sample Input 2 :

8 4
1 -4 2 10 -2 3 1 0 -20

Sample Output 2 :

Hint 1

Hint 2

Naively find sum of all subarrays of size ‘K’.

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

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’.

Time Complexity

O(N*K), where N denotes the size of array/list and K is the given integer.

For an array/list of size ‘N’, we have (N - K + 1) subarrays of size ‘K’ and we are linearly traversing each of them to calculate their sum. So, the overall time complexity is O(N*K)

Space Complexity

O(1)

Constant space is used.

(75% EXP penalty)

(100% EXP penalty)

Minimum Sum Subarray Of Given Size

Console