New update is available. Click here to update.

Last Updated: 7 Sep, 2020

Difficulty: Moderate

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

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

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

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

```
1 <= N <= 5 * 10^5
1 <= X <= 10^9
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
```

```
Try to solve in O(N) Time Complexity and O(1) Space Complexity.
```

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

Three Sum

Posted: 24 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Sort 0s, 1s, 2s

Posted: 24 Dec, 2022

Difficulty: Easy

Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: