Minimum length subarray with sum greater than given value
Filed under Morgan Stanley ยท Also reported at Mentor Graphics
Free read 3 of 3Confirm all numbers are positive, which ensures the sliding window property holds.
The question
Given an array of positive integers nums and a positive integer target, find the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Constraints
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
Examples
- Input
- target = 7, nums = [2,3,1,2,4,3]
- Output
- 2
- Why
- The subarray [4,3] has the minimal length under the problem constraint.
Approach
Confirm all numbers are positive, which ensures the sliding window property holds.
Check every possible subarray starting and ending index, calculating sums, which takes O(N^2) or O(N^3) time.
Use a sliding window (two pointers). Expand the right pointer until the window sum is >= target, then shrink from the left pointer to find the minimum length.
Total sum of array is less than target (return 0), or a single element meets the target.
Solution
O(N) time, O(1) space
class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
left, current_sum = 0, 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
Tips
- What they are testing: Test with an array where no subarray sums up to the target, and when the entire array is needed.
- Common mistake: Using nested loops resulting in O(N^2) time complexity instead of an O(N) sliding window.
Related Morgan Stanley questions
Collected from public candidate posts and coding forums. Updated Nov 2026.