Minimum Size Subarray Sum | Leetcode

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

---

Solution: Iterate through the array, maintaining a start position, the current minimum length, and the current sum from the start position to the current position. As we go through the array, shorten the subarray as much as possible by advancing the start position. If we get the current sum greater or equal to s, update the minimum length accordingly.

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;
        
        int start = 0;
        int sum = 0;
        Integer min = null;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            
            while ((start < i) && ((sum - nums[start]) >= s)) {
                sum -= nums[start];
                start++;
            }
            
            if (sum < s) continue;
            
            int curLength = i - start + 1;
            if ((min == null) || (min > curLength)) {
                min = curLength;
            }
        }
        
        return (min == null) ? 0 : min;
    }
}