Minimum Size Subarray Sum
Given an array of positive integers nums
and a positive integer target
, return the minimal length of a subarray whose sum is greater than or equal to target
. If there is no such subarray, return 0
instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3]
has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104
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))
.
Solution
We want to use a sliding window to find the minimum subarray (window).
Because the size of the window is unknown, we must use a flexible sliding window that searchs through all the valid windows that meet the requirement.
We will apply the flexible sliding window template on this question.
Our search starts on interval (0,0)
and extends rightwards before the total
reaches target
.
When the total
succeeds the target
we have found a valid subarray. Then, we start shrinking this subarray from the left finding a smaller subarray until the window is no longer valid.
Afterwards, we continue this process until we iterate through the entire array to find the minimum size subarray that has sum >= target
.
Implementation
1def minSubArrayLen(self, target: int, nums: List[int]) -> int:
2 size = len(nums)+1
3 total, l = 0, 0
4 for r in range(len(nums)):
5 total += nums[r]
6 while total >= target: # valid
7 size = min(size, r-l+1)
8 total -= nums[l]
9 l += 1
10 return size if size != len(nums)+1 else 0
The above solution using a flexible sliding window uses O(n)
time complexity. As a follow up, is there an algorithm that solves this question in O(n log(n))
?
Yes! Consider using the n
elements in nums
as a starting point of a subarray, and then use O(log(n))
time complexity to find the endpoint of that subarray.
This is can be done via a for loop and a binary search on a prefix sum array.
1def minSubArrayLen(self, target: int, nums: List[int]) -> int:
2 prefix_sum = [0]
3 for n in nums:
4 prefix_sum.append(prefix_sum[-1] + n)
5
6 size = len(nums)+1
7 for start in range(len(nums)):
8 total = 0
9 l, r, end = 0, len(nums)-1, -1
10 while l <= r:
11 mid = (l+r)//2
12 if prefix_sum[mid+1] - prefix_sum[start] >= target:
13 end, r = mid, mid - 1
14 else: l = mid + 1
15 if end != -1: size = min(size, end-start+1)
16 return size if size != len(nums)+1 else 0
Which algorithm should you use to find a node that is close to the root of the tree?
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Solution Implementation
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]
?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.