209.Minimum Size Subarray Sum

Tags: [two_pointer], [window], [shrink_window], [dp], [binary_search]

Com: {fb}

Link: https://leetcode.com/problems/minimum-size-subarray-sum/#/description

Given an array of n positive integers and a positive integers, find the minimal length of a contiguous 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]ands = 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 theO(n) solution, try coding another solution of which the time complexity isO(nlogn).

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

Solution: Two Pointer, Shrink Window

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        min_len = len(nums) + 1
        tmp_sum = 0
        start = 0
        end = 0
        while end < len(nums):
            tmp_sum += nums[end]
            if tmp_sum >= s:
                # shrink the window, by moving the start to right side.
                while tmp_sum - nums[start] >= s:
                    # the start must <= end, because s is a positive integer, 
                    # and the tmp_sum is the sum of the subarray[start:end + 1], so start cannot > end.
                    tmp_sum -= nums[start]
                    start += 1

                min_len = min(min_len, end - start + 1)
                tmp_sum -= nums[start]
                start += 1

            end += 1

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

Revelation:

• When we shrink the window, in the while loop, we don't need check whether start <= end, the reason has been explained in the comments.
• The above algorithm, only fit the given array, which has all positive integers. If the given contains the negative numbers such as, [2, 1, 5, -10, 11, 0, 7], and s = 8, the above algorithm will not give out the correct result. Explanation: Since given array contains only positive integers, the subarray's sum can only increase by including more elements. so, you don't have to include more elements once the current subarray already has a sum, which is large enough.
• I think the above algorithm also fit the given array who contains 0s.

Note:

• Time complexity = O(n), n is the number of element of the given array.
• Space complexity = O(1).

Follow Up Solution: DP, Binary Search

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        size = len(nums)
        left_sums = [0 for _ in xrange(size)]
        left_sums[0] = nums[0]
        for i in xrange(1, size):
            left_sums[i] = left_sums[i - 1] + nums[i]

        min_len = size + 1
        for start in xrange(size):
            # Because all elements of the nums are positive integers, 
            # so the elements of left_sums are sorted ascending. 
            # So we can apply the binary search on it.
            target = s
            if start - 1 >= 0:
                target += left_sums[start - 1]
            end = self.binary_search(left_sums, start, size - 1, target)
            if end < 0:
                continue

            min_len = min(min_len, end - start + 1)

        return min_len if min_len <= size else 0

    def binary_search(self, arr, start, end, target):
        while start <= end:
            mid = start + (end - start) / 2
            if arr[mid] < target:
                start = mid + 1
            else:
                if mid - 1 < start or arr[mid - 1] < target:
                    return mid
                end = mid - 1

        return -1

Revelation:

• The above algorithm only fit the given array whose elements are all positive integers.
• I think the above algorithm also fit the given array who contains the 0s.

Note:

• Time complexity = O(nlgn), n is the number of elements of the given array.
• Space complexity = O(n), n is the number of elements of the given array.