Minimum Size Subarray Sum

Question (LC.209)

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s.

Example

I: nums = [2,3,1,2,4,3], s = 7
O: 7 because [4,3]

Analysis

The brute force approach is just to try all possible subarrays then keep the shortest length.

Code

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int currentSum = 0;
    int minLength = Integer.MAX_VALUE;

    // from this number the smallest window
    for (int i = 0; i < nums.length; i++) {
        currentSum = 0;
        for (int j = i; j < nums.length; j++) {
            currentSum += nums[j];
            if (currentSum >= s) {
                minLength = Math.min(minLength, j - i + 1);
                break;
            }
        }
    }
    return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}

Optimization

The brute force solution is O(n^2) because the pointer j will go back to where i is for every nested loop. The best way to see the overlapping subproblems is to run through some examples.

[2,3,1,2,4,3], 7

A   2  3  1  2  4  3

L1  i        j
L2     i  j   <--we already know this won't be a solution
                -j should at least start from index 3

j doesn't have to go back to i every time. Instead of scanning every window, we "shrink" the window then extend it on the other end.

A   2  3  1  2  4  3

L1  i------->j
L2     i------->j
L3        i---->j
L4           i---->j
L5              i->j

Optimized Code

We want to shrink then extend but this won't work for the first iteration. So instead we want to shrink before we get to the next iteration.

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int currentSum = 0;
    int minLength = Integer.MAX_VALUE;
    int j = 0;
    // from this number the smallest window
    for (int i = 0; i < nums.length; i++) {
        // extend the window
        while (j < nums.length && currentSum < s) {
            currentSum += nums[j++];
        }
        // check the window sum
        if (currentSum >= s) {
            int windowSize = j - i; // no +1 b/c j++ after fit window
            minLength = Math.min(minLength, windowSize);
        }
        // shrink before next iteration
        currentSum -= nums[i];
    }
    return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}

This gives O(n) time complexity.