209. Minimum Size Subarray Sum

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. If there isn't one, return 0 instead.

Example:

Input:
s = 7, nums = [2,3,1,2,4,3]
Output:2

Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

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

Thoughts:

1. O(n): Having a left and right pointer, Scan through the array, if record the sum if arr[i...j] >=s, then compare min with current sum, then try to move left pointer up, then compare with min again.

2. O(nlogn) Binary Search:

Code: O(n):

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length == 0 ) return 0;

        int i = 0, j = 0 , sum = 0 , min = Integer.MAX_VALUE;
        while(j < nums.length){
            sum += nums[j++];
            while(sum >=s){
                min = Math.min(min, j - i); //(old j) - i + 1 = j - i
                sum -= nums[i++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

Code: Another C++

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
        while (j < nums.length) {
            while (sum < s && j < nums.length) sum += nums[j++];
            if(sum>=s){
                while (sum >= s && i < j) sum -= nums[i++];
                min = Math.min(min, j - i + 1);
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

Python

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        i, j, pres, res = 0 , 0 , 0, len(nums) + 1

        while j < len(nums):
            pres += nums[j]; j += 1
            while pres >= s:
                res = min(res, j - i)
                pres -= nums[i]; i+= 1
        return res if res != len(nums) + 1 else 0

Code: O(nlogn) - search if a window of size k that satisfies the condition

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 1, j = nums.length, min = 0;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (windowExist(mid, nums, s)) {
                j = mid - 1;
                min = mid;
            } else i = mid + 1;
        }
        return min;
    }


    private boolean windowExist(int size, int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i >= size) sum -= nums[i - size];
            sum += nums[i];
            if (sum >= s) return true;
        }
        return false;
    }
}

Python

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        i,j, res = 1, len(nums), 0

        def windowExists(size): # for a fixed window size "size": whether there is window sum >= s
            acc = 0
            for i in range(len(nums)):
                acc += nums[i]
                if i >= size: acc -= nums[i - size]
                if acc >= s:
                    return True
            return False

        while i <= j:
            mid = (j - i >> 1) + i
            if windowExists(mid):
                j = mid - 1
            else:
                i = mid + 1

        return i if i <= len(nums) else 0