0
\$\begingroup\$

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));
    }
}
\$\endgroup\$
  • \$\begingroup\$ I may be wrong, but after looking briefly at your solution, it doesn't look correct to me. \$\endgroup\$ – George Barwood Feb 3 at 21:52
  • \$\begingroup\$ @GeorgeBarwood - thanks for looking. What doesn't look correct? Thanks. \$\endgroup\$ – marathon Feb 3 at 22:35
  • \$\begingroup\$ 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. \$\endgroup\$ – George Barwood Feb 3 at 23:00
  • \$\begingroup\$ yeah, it comes up with the wrong result for {1, -4, -45, 6, -6, 19, 16, -1, 18} \$\endgroup\$ – marathon Feb 4 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.