# In an Array, find the Smallest Subarray with Sum Greater than the Given Value

Objective: Given an array and an integer, find the smallest subarray whose sum is greater than the given integer.

Examples:

```arrA[] = { 1, 5, 20, 70, 8}
Integer = 97
Output : Min Length = 3 Subarray = [20, 70, 8]

arrA[] = { 1, 10, 3, 40, 18}
Integer = 50
Output : Min Length = 2 Subarray = [40, 18]
```

Approach:

Naive Approach: Use 2 loops . Time Complexity – O(n2).

Better Approach: Time Complexity – O(n)

• Initialize minLength = length of the array and say the given integer is x.
• Take variables currSum = 0, start = 0
• Do the linear scan in array and start adding each element to the currSum.
• if currSum > x then start subtracting element from the start.(currSum-arrA[start]) check the length of the subarray, if it is less then the minLength (currentIndex-start<minLength)update minLength and store the current index and start index for finding the subarray.

Complete Code:

Output:

```Min length of subarray to get 50 is : 2
SubArray is:   40   18
```

__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

### 8 Responses

1. sagivo says:

it would work only if the array is sorted. if not, it would fail.
a = [1, 20, 30, 10, 50], min = 51
will return [1, 20, 30] instead of [1, 50]

• tutorialhorizon says:

The code will return Minimum length of subarray to get 51 is : 2
SubArray is: 10 50

The program is correct

2. Princ says:

This code returns 40 and 18 for me.

3. dheeraj singhal says:

for array a={ 1, 20, 30, 10} and sum 60, above code will print only length not subarray. Little modification is required in code as mentioned below.

if (i – start < minLen)

it should be
if (i – start <= minLen)

4. Eric Gill says:

Hello,

Given an array {4, 7, 11, 3, 12, 1, 9, 2} and x=22 it returns 11, 3 and 12 as the shortest subarray when {11, 12} is the correct answer.

• tutorialhorizon says:

Yes , the program is for subarray so elements has to be contiguous so 11,3,12 is the right answer. {11,12} is the sub sequence.

5. Ali Issa says:

This line should be added before the loops: arrA = arrA.sort((a, b) => a > b)