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