# Find the smallest subarray with sum greater than a given value

Given some array, find the smallest subarray with a sum that is greater than a value given.

So for instance, given this array:

{1, -4, -45, 6, 0, 19, 16, 17}


and the give value of 51, the smallest subarray with a sum greater than 51 would be {19, 16, 17}

The idea is to use a window to scan over the elements, expanding it on the right and contracting it on the left as needed.

public class SmallestSubarray {

static int[] smallestSub(int[] arr, int targetSum) {
int winnerL = 0, winnerR = Integer.MAX_VALUE;
int currentSum = 0;
int leftI = 0;
//widen the window from the right side
for (int rightI = 0; rightI < arr.length; rightI++) {
currentSum += arr[rightI];

//handle negatives, collapse the window
if (currentSum < 0) {
//move L past R because R is going to increment next... otherwise left will be sitting on the wrong value
leftI = rightI + 1;
if (leftI == arr.length) {
return new int[0];
}
currentSum = 0;
continue;
}
// now we've built up a sum greater than target.  trim it down if possible
while (currentSum > targetSum && leftI <= rightI) {
// if current window is smaller than the last smallest window
if (rightI - leftI  < winnerR - winnerL) {
winnerL = leftI;
winnerR = rightI;
}
//chip away at current sum and shrink window from left.
currentSum -= arr[leftI++];
}
}
if (winnerR == Integer.MAX_VALUE) {
return new int[0];
}
return Arrays.copyOfRange(arr, winnerL, winnerR +1);
}

public static void main(String[] args) {
int[] arr2 = {1, -4, -45, 6, 0, 19, 16, 17};
int[] result = smallestSub(arr2, 51);
System.out.println("Arrays.toString(result) = " + Arrays.toString(result));
}
}

• I may be wrong, but after looking briefly at your solution, it doesn't look correct to me. – George Barwood Feb 3 at 21:52
• @GeorgeBarwood - thanks for looking. What doesn't look correct? Thanks. – marathon Feb 3 at 22:35
• I don't think your "trim it down" code is correct. currentSum could temporarily dip below targetSum but then come back up again ( and you will not see that ). Imagine going for a hike and trying to note all climbs of more than 51 feet. – George Barwood Feb 3 at 23:00
• yeah, it comes up with the wrong result for {1, -4, -45, 6, -6, 19, 16, -1, 18} – marathon Feb 4 at 1:58