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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.