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

**Complete Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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

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

This code returns 40 and 18 for me.

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.

instead of

if (i – start < minLen)

it should be

if (i – start <= minLen)

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.

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

No need to sort the array. The program will work without sorting as well