The original question can be found here.
The question is asking us to the minimum length of subarray that it’s sum is no less than target value.
Brute Force
The brute force we can immediately think of is to enumerate all subarrays and keep track of the minimum length.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = float('inf')
for i in range(0, len(nums)):
sum = 0
for j in range(i, len(nums)):
sum += nums[j]
if sum >= target:
min_length = min(min_length, j - i + 1)
break
return 0 if min_length == float('inf') else min_lengthTime Complexity: O(n^2). Space Complexity: O(1).
Binary Search
You may ask: this array is not sorted, why can we use binary search? Well, though the array is not sorted, but the prefix sum is sorted since all the numbers in array are positive. If you’re not familiar with prefix sum, please look at my another post here.
nums: [2, 3, 1, 2, 4, 3] target: 7
prefix: [0, 2, 5, 6, 8, 12, 15]For each prefix sum x, we try to find the smallest y that y - x >= 7. A standard binary search question, right?
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length, sum = float('inf'), 0
prefix_sum = [sum]
for num in nums:
sum += num
prefix_sum.append(sum)
for index, element in enumerate(prefix_sum):
the_other_index = self.binary_search(prefix_sum, index + 1, target + element)
if the_other_index != -1:
min_length = min(min_length, the_other_index - index)
return 0 if min_length == float('inf') else min_length
def binary_search(self, sums: List[int], start_index: int, target: int) -> int:
if start_index >= len(sums):
return -1
left, right = start_index, len(sums) - 1
while left + 1 < right:
mid = (left + right) // 2
if sums[mid] < target:
left = mid
else:
right = mid
if sums[left] >= target:
return left
if sums[right] >= target:
return right
return -1Time Complexity: O(nlgn). Space Complexity: O(n).
2 Pointers
We maintain a sliding window, and make sure the window always have just enough elements that their sum is no less than target. To achieve this, we first expand the right pointer until the sum of elements inside sliding window is no less than target. Then we shrink the left pointer and make sure the sum in sliding window is still no less than target.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left, right = 0, 0
min_length = float('inf')
sum = nums[0]
while left < len(nums):
while sum < target and right + 1 < len(nums):
right += 1
sum += nums[right]
if sum < target:
break
while sum >= target:
min_length = min(min_length, right - left + 1)
sum -= nums[left]
left += 1
return 0 if min_length == float('inf') else min_lengthTime Complexity: O(n). Space Complexity: O(1).