209. Minimize Size Subarray Sum

Problem

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(n log n).

Thought Process

  • loop thru the array, if sum >= s exits, return 1
  • create a window, for window of length from 2 to n
    • if sum >= s, return window length
    • loop thru to window length of n
  • return 0, if no such window is found

White Board

Below is the white board:

Code

class Solution:
    def msa(self, nums, s):
        temp = []
        for i in range(len(nums)):
            for j in range(len(nums)):
                if sum(nums[i:j+1]) >= s:
                    temp.append(len(nums[i:j+1]))

        if temp:
            return min(temp)

        return 0

def test_msa():
    nums = [1,2,3,4,5]
    s = 15
    msa = Solution().msa(nums, s)

    print(msa)

test_msa()
5

Complexity

  • This brute force solution has a time complexity of O(n**3), as will loop thru all sub-arrays via two pointers O(n**2), within each iteration, sum an array is also O(n)
  • The space complexity is O(n), as I created a space temp

Even the result is correct but it will not pass lc as the max time is reached.

Optimization

The brute force solution wasted to many resources on constantly calculating sums of all sub-arrays


class Solution2:
    def msa_2(self, nums, s):
        l, r = 0, -1
        # nums[l:r], initially empty
        sum = 0
        res = len(nums) + 1
        # impossible to reach, an invalid result

        while(l < len(nums)):
            if (sum < s) and (r + 1 < len(nums)):
                # if sum is smaller, keep moving right index to increase window
                r += 1
                sum += nums[r]

            else:
                # if sum >= s, move left index to shrink window
                sum -= nums[l]
                l += 1

            if sum >= s:
                # if sum is found
                res = min(res, r - l + 1)
                # r - l + 1 as the segment are close on both end

        if(res == len(nums) + 1):
            # if no solution is found
            return 0

        return res

def test_msa2():
    nums = [1,2,3,4,5]
    s = 15
    msa2 = Solution2().msa2(nums, s)

    print(msa2)

test_msa()
5

Time complexity is O(n), as only did one round of iteration; Space complexity is O(1) since no new space is used