Smallest Subarray with sum greater than a given value

The problem, simply

You get an array of non-negative numbers and a number x. Find the shortest stretch of numbers next to each other whose sum is strictly greater than x. Give back its length.

If no stretch has a sum greater than x, give back 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start. From each start, add numbers to the right until the sum passes x. That is the shortest run from this start, so stop there and move to the next start.

class Solution {
    public int smallestSubWithSum(int[] arr, int x) {
        int n = arr.length, best = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum > x) {                       // the first time it passes x
                    best = Math.min(best, j - i + 1);
                    break;                           // longer runs from i are worse
                }
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

How long it takes: up to n starts, each walking up to n steps, O(n^2). Extra room: a few numbers, O(1).

Way 2: the clever way

Keep a window [start, end] and its sum.

1. Move end right one step at a time and add arr[end] to the sum.
2. While the sum is greater than x: write down the length end - start + 1 if it is the best so far, then remove arr[start] and move start right.
3. At the end, return the best length, or 0 if nothing was written down.

Each number joins the window once and leaves once. That is why this is fast.

class Solution {
    public int smallestSubWithSum(int[] arr, int x) {
        int best = Integer.MAX_VALUE, start = 0;
        long sum = 0;
        for (int end = 0; end < arr.length; end++) {
            sum += arr[end];                     // stretch on the right
            while (sum > x) {                    // more than enough: squeeze on the left
                best = Math.min(best, end - start + 1);
                sum -= arr[start];
                start++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

How long it takes: end moves n times and start moves at most n times in total, O(n). Extra room: a few numbers, O(1).

Watch out for

• Return 0 when nothing works. Do not return Integer.MAX_VALUE.
• The window trick needs non-negative numbers. With a negative number, dropping from the left could raise the sum, and the squeeze logic breaks.
• Sums of many big numbers can overflow an int. Keep sum in a long.

What interviewers ask next

• What if the array can have negative numbers (LeetCode 862)? Use prefix sums and a deque that keeps prefix indexes in increasing order of prefix value. O(n).
• A different O(n log n) way for non-negative numbers: build prefix sums, which only go up, and for each start binary search the first end whose prefix is more than prefix[start] + x.
• Longest stretch with sum at most x. Same window, but now you record the length while the sum is small enough.
• Count stretches with sum exactly k. With negatives allowed, use a hash map of prefix sums and how often each appeared.

Remember this

Grown-up words: the frame is a variable-size sliding window, a stretch of numbers next to each other is a subarray, and the stretch and squeeze moves are the two pointers of the window.