**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(n^{2}).

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

__________________________________________________

### Like this:

Like Loading...

*Related*