Last Updated: 7 Sep, 2020
Minimum Subarray With Required Sum
Moderate
Asked in companies
You have been given an array(ARR) of positive integers and an integer X. You have to find the minimum length subarray such that the sum of all of its elements is strictly greater than the given integer X.
Note:
A subarray is a contiguous block of elements that can be formed by deleting some (possibly zero) elements from the beginning or the end of the original array.
For example :
If the given array is [1, 2, 3, 4, 5], then [2, 3, 4], [1, 2], [5] are some subarrays while [1, 3], [2, 3, 5] are not.
If there are multiple subarrays with minimum length, find one which appears earlier in the array (i.e. subarray that starts with lower index).
If there is no such subarray, print an empty line.
Input Format:
The first line of input contains two integers 'N' and 'X' separated by a single space. 'N' represents the size of the given array/list and 'X' represents the given integer.
The second line of input contains 'N' single space-separated integers representing the elements of the array/list.
Output Format :
The only line of output contains single space-separated elements of the minimum length subarray.
You do not need to print anything explicitly, it has already been taken care of.
Constraints :
1 <= N <= 5 * 10^5
1 <= X <= 10^9
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Follow Up :
Try to solve in O(N) Time Complexity and O(1) Space Complexity.
Approaches
We can check every subarray of the array/list if it’s sum is greater than X(given integer) or not. To do this, we traverse for every possible start and endpoint of the subarray using two nested loops. We will keep updating the ‘sum’ while expanding our endpoint. Out of all the valid(sum greater than X) subarrays, we pick the minimum length subarray.
The idea is to do Binary Search over the answer(i.e. Length of the subarray). But how did we come to this conclusion? We know that we can find out if there is a subarray of length K with the sum greater than ‘X’ in linear time using the sliding window technique.
Also,
- We know that if a subarray of length K is valid (sum greater than X), then there must be a valid subarray of length greater than K.
- And if there is no valid subarray of length K, we know for sure that there will not be a valid subarray of length less than K.
The above two facts resemble the property of a monotonic function and hence we can use Binary Search on the length of the subarray to find our minimum length subarray with a sum greater than ‘X’.
The idea is to use two pointers technique with a sliding window of variable length. The current window will be our current processing subarray. If the sum of the current window is greater than X (given integer), it makes no sense in expanding the length of the window (because the sum will only increase in doing so). Similarly, if the sum is less than X, there is no benefit in shrinking the window.
We will keep track of the minimum length subarray obtained so far and only update it when we find a subarray of smaller length.
Here, is the complete algorithm-
- Initialize ‘start’ and ‘end’ pointers to 0, as currently, our window has size 1.
- Initialize ‘sum’ to 0, which will store the sum of the current window/subarray.
- Initialize ‘minimumLength’ to infinite.
- Loop till ‘end’ < ‘arraySize’
- Add arr[end] to the window i.e. ‘sum’ += arr[end]
- Shrink window till ‘sum’ is greater than ‘X’
- Update ‘minimumLength’ if the current window is shorter.
- Remove arr[start] from the window i.e. ‘sum’ -= arr[start].
- Shrink window size i.e. Increment start pointer by 1.
- Expand window size i.e. Increment end pointer by 1.
- Return ‘minimumLength’.
Similar problems