#209 Minimum Size Subarray Sum
frequently reported atByteDance / TikTokBloombergMicrosoftAmazonMetaGoogle
the problem
In plain words
Given positive integers nums and a positive target, return the minimal length of a contiguous subarray whose sum is ≥ target, or 0 if none exists.
in target = 7, nums = [2,3,1,2,4,3]
out 2
[4,3].
in target = 4, nums = [1,4,4]
out 1
[4] alone is enough.
in target = 11, nums = [1,1,1,1,1,1,1,1]
out 0
- 1 ≤ target ≤ 10⁹
- 1 ≤ n ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (variable size)
All numbers are positive, so adding grows the sum and removing shrinks it. Once the window reaches target, shrinking from the left is the only way to make it shorter.
solutions
From brute force to optimal
From each start, add numbers until the sum reaches target.
- For each i: sum from i rightwards.
- At the first j with sum ≥ target, record j − i + 1 and stop.
Up to n steps from each of n starts.
A running sum.
class Solution { public int minSubArrayLen(int target, int[] nums) { int best = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; if (sum >= target) { // longer windows from i can't be shorter best = Math.min(best, j - i + 1); break; } } } return best == Integer.MAX_VALUE ? 0 : best; }}Prefix sums are strictly increasing (positive numbers), so binary search the end for each start.
- prefix[i] = sum of the first i numbers.
- For each i, binary search the smallest j with prefix[j] ≥ prefix[i] + target.
- Length is j − i.
n binary searches over n + 1 prefix values.
The prefix array.
class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length; long[] prefix = new long[n + 1]; // prefix[i] = sum of the first i numbers for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i]; int best = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { long want = prefix[i] + target; // smallest j with prefix[j] >= want int lo = i + 1, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (prefix[mid] >= want) hi = mid; else lo = mid + 1; } if (prefix[lo] >= want) best = Math.min(best, lo - i); } return best == Integer.MAX_VALUE ? 0 : best; }}Grow right; while sum ≥ target, record the length and shrink left.
- left = 0, sum = 0.
- sum += nums[right].
- While sum ≥ target: best = min(best, right − left + 1); sum −= nums[left++].
- Return best, or 0 if never set.
left and right each move at most n times.
Three integers.
class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0, sum = 0, best = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= target) { // valid: record it, then shrink best = Math.min(best, right - left + 1); sum -= nums[left++]; } } return best == Integer.MAX_VALUE ? 0 : best; }}Dry run
in the room
How to say it in the interview
talk track
- Say why positivity matters: "removing an element always lowers the sum, so shrinking is safe".
- LeetCode's follow-up asks for an O(n log n) solution — that's the prefix + binary search version.
traps
- Returning
Integer.MAX_VALUEwhen no window exists — the problem wants 0.
what they ask next
Follow-ups
What if numbers could be negative?
The window no longer works. Use prefix sums with a monotonic deque (LC 862, Shortest Subarray with Sum at Least K).
before you submit
Edge cases to test
- No subarray reaches target → 0, never
Integer.MAX_VALUE. - One number already ≥ target → 1.
- Only the whole array is enough → n.
- The sum stays below target + 10⁴ ≤ 1,000,010,000 before each shrink, so
intis safe here — say so out loud.
practise next
Similar problems
- #76Minimum Window SubstringHardin Sliding Window
- #862Shortest Subarray with Sum at Least KHardin Queues
- #560Subarray Sum Equals KMediumin Hashing