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

### 8 thoughts on “In an Array, find the Smallest Subarray with Sum Greater than the Given Value”

1. 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]

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

The program is correct

2. This code returns 40 and 18 for me.

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

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