Minimum Size Subarray Sum

NeetCode: Minimum Size Subarray Sum · LeetCode: 209. Minimum Size Subarray Sum · Difficulty: Medium

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0.

Example

Text

Input:  target = 7,  nums = [2, 3, 1, 2, 4, 3]       Output: 2   (the subarray [4, 3])
Input:  target = 4,  nums = [1, 4, 4]                Output: 1
Input:  target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1] Output: 0

Brute force: try every start and extend

For every start index, keep adding elements to the right until the running sum reaches target, and record the length. Sums are kept in long because the total of many int values can exceed Integer.MAX_VALUE, and int addition wraps silently. Because all numbers are positive, the first time the sum reaches target is the shortest subarray for that start, so extending stops there.

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int best = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            long sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum >= target) {
                    best = Math.min(best, end - start + 1);
                    break;
                }
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minSubArrayLen(7, new int[] {2, 3, 1, 2, 4, 3}));
        System.out.println(s.minSubArrayLen(4, new int[] {1, 4, 4}));
        System.out.println(s.minSubArrayLen(11, new int[] {1, 1, 1, 1, 1, 1, 1, 1}));
        System.out.println(s.minSubArrayLen(3, new int[] {}));
    }
}

Output

Time: O(n^2). Space: O(1).

Better: prefix sums and binary search

Let prefix[i] be the sum of the first i elements. The sum of nums[i..j] is prefix[j] - prefix[i]. Since every element is positive, prefix is strictly increasing, so for each i a binary search (written out as a loop, a lower bound over prefix) finds the smallest j with prefix[j] >= prefix[i] + target. That gives n searches of O(log n) each. It costs O(n) extra memory and relies on the elements being positive.

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long need = prefix[i] + target;
            // first index j with prefix[j] >= need (n + 1 if there is none)
            int lo = i + 1, hi = n + 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (prefix[mid] < need) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            if (lo <= n) {
                best = Math.min(best, lo - i);
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minSubArrayLen(7, new int[] {2, 3, 1, 2, 4, 3}));
        System.out.println(s.minSubArrayLen(4, new int[] {1, 4, 4}));
        System.out.println(s.minSubArrayLen(11, new int[] {1, 1, 1, 1, 1, 1, 1, 1}));
        System.out.println(s.minSubArrayLen(3, new int[] {}));
    }
}

Output

Time: O(n log n). Space: O(n).

Optimal: sliding window

Grow the window by moving right, adding each element to the running sum. Whenever the sum is at least target, the window is valid: record its length, then shrink from the left (subtracting nums[left]) for as long as it stays valid, because a shorter valid window may exist. Positivity is what makes this correct: extending a window never lowers its sum and shrinking never raises it, so left and right only ever move forward and each moves at most n times.

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int best = Integer.MAX_VALUE;
        int left = 0;
        long sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minSubArrayLen(7, new int[] {2, 3, 1, 2, 4, 3}));
        System.out.println(s.minSubArrayLen(4, new int[] {1, 4, 4}));
        System.out.println(s.minSubArrayLen(11, new int[] {1, 1, 1, 1, 1, 1, 1, 1}));
        System.out.println(s.minSubArrayLen(3, new int[] {}));
    }
}

Output

Time: O(n), since each index enters and leaves the window once. Space: O(1).