MediumNo. 0209
Minimum Size Subarray Sum — LeetCode 209 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Binary Search, Prefix Sum, Sliding Window
- On a study list
- Top Interview 150
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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
- 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.
Python solution
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
s = list(accumulate(nums, initial=0))
ans = n + 1
for i, x in enumerate(s):
j = bisect_left(s, x + target)
if j <= n:
ans = min(ans, j - i)
return ans if ans <= n else 0Complexity
- Time
- <code>O(n log(n))</code>
- Space · auxiliary
- O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 209. Minimum Size Subarray Sum is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0713 | Subarray Product Less Than K | Medium |
| 0862 | Shortest Subarray with Sum at Least K | Hard |
| 1004 | Max Consecutive Ones III | Medium |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard |
| 2302 | Count Subarrays With Score Less Than K | Hard |
| 2398 | Maximum Number of Robots Within Budget | Hard |
Frequently asked questions
- How hard is LeetCode 209. Minimum Size Subarray Sum?
LeetCode 209. Minimum Size Subarray Sum is rated Medium on LeetCode.
- What is the time complexity of LeetCode 209. Minimum Size Subarray Sum?
The Python solution on this page runs in <code>O(n log(n))</code>.
- What is the space complexity of LeetCode 209. Minimum Size Subarray Sum?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 209. Minimum Size Subarray Sum cover?
LeetCode 209. Minimum Size Subarray Sum is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.