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.
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).
- 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
Below is the white board:
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()
- 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.
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()
Time complexity is O(n), as only did one round of iteration; Space complexity is O(1) since no new space is used