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

Objec­tive: Given an array and an inte­ger, find the small­est sub­ar­ray whose sum is greater than the given integer.

Exam­ples:

```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 Com­plex­ity — O(n2).

Bet­ter Approach: Time Com­plex­ity — O(n)

• Ini­tial­ize min­Length = length of the array and say the given inte­ger is x.
• Take vari­ables currSum = 0, start = 0
• Do the lin­ear scan in array and start adding each ele­ment to the currSum.
• if currSum > x then start sub­tract­ing ele­ment from the start.(currSum-arrA[start]) check the length of the sub­ar­ray, if it is less then the min­Length (currentIndex-start<minLength)update min­Length and store the cur­rent index and start index for find­ing the subarray.

Com­plete Code:

Out­put:

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

#### You may also like...

• sagivo

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]

• tuto­ri­al­hori­zon

The code will return Min­i­mum length of sub­ar­ray to get 51 is : 2
Sub­Ar­ray is: 10 50

The pro­gram is correct

• Princ

This code returns 40 and 18 for me.

• dheeraj sing­hal

for array a={ 1, 20, 30, 10} and sum 60, above code will print only length not sub­ar­ray. Lit­tle mod­i­fi­ca­tion is required in code as men­tioned below.