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

 public class MinimumSubArraySum { public void minSubArray(int[] arrA, int x) { int start = 0; int ansEnd = 0; int ansStart = 0; int currSum = 0; int minLen = arrA.length; boolean found = false; for (int i = 0; i <= arrA.length; i++) { while (currSum >= x) { found = true; currSum = currSum – arrA[start]; if (i – start <= minLen) { minLen = (i – start); ansEnd = i; ansStart = start; } start++; } if (i < arrA.length) { currSum = currSum + arrA[i]; } } if(found){ System.out.println("Minimum length of subarray to get " + x + " is : " + minLen); System.out.print("SubArray is:"); for (int i = ansStart; i < ansEnd; i++) { System.out.print(" " + arrA[i]); } }else{ System.out.println("No subarray to get " + x); } } public static void main(String[] args) throws java.lang.Exception { int[] arrA = { 1, 5, 4, 40 }; MinimumSubArraySum i = new MinimumSubArraySum(); i.minSubArray(arrA, 50); } }

Output:

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