Problem

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.

Solution:

Approach 1: with time O(n)

1. create prefix sum array of size n + 1 for all elements of nums from i = 0 to n - 1 mapping to i = 1 to n with preSums[0] = 0

2. use a deque and a local variable curSum To loop thru preSums:

   1. append preSum[i] if the curSum < s
   2. record length and deque.popleft() if curSum >= s

3. return the shortest length

Approach 2: with time O(n log n)

1. create prefix sum array like Approach one
2. loop thru prefix sum, for each element i,
   1. binary search to find the smallest following element j, such that preSums[j] - preSums[i] >= s
3. return result

be careful with return conditions. Read problem carefully. and Remember to mark the problem in code. write the code immediately for careful return conditions

Python Solution:

time O(n)

import sys
from collections import deque
class Solution(object):


    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """

        # there isn't one, return 0 instead.
        q = deque()
        i = 0
        n = len(nums)
        curSum = 0
        resLen = sys.maxint
        while i < n:
            while i < n and curSum < s:
                q.append(nums[i])
                curSum += nums[i]
                i += 1
            while curSum >= s:
                resLen = min(resLen, len(q))
                curSum -= q.popleft()
        if resLen == sys.maxint:
            return 0
        return resLen

time O(n log n )

import sys

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

    def solveNlogN(self, s, nums):
        n = len(nums)
        preSums = [0] * (n+1)
        # setup prefix sums 
        for i in range(n):
            preSums[i+1] = preSums[i] + nums[i]

        # for each i, the rest of it can be binary searched to find out the result
        res = sys.maxint
        for i in range(n):
            temp = self.binarySearch(i + 1, n, preSums, s, i)
            res = min(temp , res)

        if res == sys.maxint:
            return 0
        else:
            return res

    def binarySearch(self, l, r, preSums, s, start):

        while l + 1 < r:
            mid = l + (r - l) / 2
            if preSums[mid] - preSums[start] >= s:
                r = mid
            else:
                l = mid
        if preSums[l] - preSums[start] >= s:
            return l - start
        elif preSums[r] - preSums[start] >= s:
            return r - start
        else:
            return sys.maxint