Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Grow a window by adding nums[right]; whenever the window sum ≥ target, shrink from the left while recording the smallest valid length. Because all values are positive, the sum is monotonic, so a variable-size sliding window finds the shortest qualifying subarray in O(n). Return 0 if none exists.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise a variable-size sliding window and exploit the positivity guarantee to keep it O(n). They want to see you shrink with a while-loop and prove the amortized linear bound, not just write a nested-loop O(n²).
Where candidates slip
Using an `if` instead of a `while` to shrink (so the window never contracts fully), recording the length at the wrong moment, or returning ∞/−1 instead of 0 when no subarray qualifies.
How to stand out
Call out *why* it's O(n): 'each index is added once by right and removed at most once by left, so the inner while runs ≤ n times total across the whole scan.' Then note the positivity precondition is what licenses the greedy shrink.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewleft=0, sum=0, best=∞sum >= target?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — All Subarrays
1Hint 1Explore hintHide hint
What's the most direct way to find the shortest qualifying subarray, ignoring efficiency?
2Hint 2Explore hintHide hint
Fix a start index i, extend the end j while accumulating the sum, and the moment sum >= target record (j - i + 1) and break.
3Hint 3Explore hintHide hint
Two nested loops with a running inner sum gives O(n²). It works but re-scans overlapping ranges repeatedly.
A · Core idea
For every start index i, extend the end j and accumulate the sum. As soon as the running sum reaches target, the window [i, j] is the shortest qualifying one starting at i — record its length and break to the next i.
Why it's the natural baseline. The problem is literally 'find a contiguous range with sum ≥ target', and the most direct reading is 'try every contiguous range'. Maintaining a running inner sum (rather than re-summing from scratch with a third loop) is the one optimization to mention here so you don't accidentally describe an O(n³).
Why it's wasteful. When we advance the start from i to i+1, brute force throws away everything it learned and re-accumulates from the new start. But the windows overlap massively — the work for start i+1 largely repeats start i. For n = 10⁵, O(n²) is ~10¹⁰ operations and times out.
The insight it surfaces. Watching brute force, you notice that once a window from i reaches the target, sliding the start forward and reusing the accumulated sum (subtracting the element that leaves) would avoid all the recomputation. That reuse — possible only because values are positive — is exactly the sliding window.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
target = 7, nums = [2, 3, 1, 2, 4, 3]i=0
2,5,6,8≥7 at j=3 → len 4
best=42C · Code with teaching comments
Reference implementation previewpublic int minSubArrayLen(int target, int[] nums) { int n = nums.length; int best = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int sum = 0;Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Brute force recomputes overlapping sums from scratch for every start index. The redundancy is the tell: maintain one running sum and slide the boundaries instead of restarting — that's the leap to O(n).
ComplexityO(n²) time, O(1) space — For each of n start indices we may scan up to n endpoints → O(n²) time. A single running sum keeps it O(1) extra space (avoid an inner third loop that would make it O(n³)).
E · Edge cases and pitfalls3Adding a third inner loop to re-sum each window → O(n³).Explore edge casesHide edge cases
Pitfalls
- Adding a third inner loop to re-sum each window → O(n³).
- Forgetting to break after the first qualifying j → unnecessary extra work.
- Returning MAX_VALUE/inf instead of 0 when no subarray qualifies.
Approach 2 of 2 · Optimal
Variable-Size Sliding Window (Optimal)
1Hint 1Explore hintHide hint
Reuse the running sum instead of restarting. Keep a window [left, right]; what should you do the moment its sum reaches target?
2Hint 2Explore hintHide hint
Expand right to grow the sum. Whenever sum >= target, the window is valid — try to shrink from the left while it stays valid, recording the length each time.
3Hint 3Explore hintHide hint
Use a while-loop to shrink (not an if), and record (right - left + 1) before subtracting nums[left]. Each index is added once and removed once → O(n).
A · Core idea
Maintain a window [left, right] and a running sum. Move right across the array adding nums[right]. Each time sum >= target, the current window qualifies — record right - left + 1 as a candidate answer, then subtract nums[left] and advance left to see if a shorter window still qualifies. Keep shrinking while the sum stays at or above target.
Why shrinking greedily is correct — the positivity guarantee. Every value is positive, so the window sum is strictly monotonic in the window's boundaries: extending right can only increase the sum, and advancing left can only decrease it. That monotonicity is what lets us shrink without fear: once the sum drops below target, no further left-shrink at this right can recover it, so we can stop shrinking and grow right again. With negative numbers this collapses — removing a negative could increase the sum — which is exactly why the problem specifies positive integers and why the sliding window is the intended tool.
Why a `while`, not an `if`, and why record before subtracting. After adding nums[right] the sum might overshoot the target by a lot, meaning several left elements could be peeled off and the window would still be valid. A single if would remove only one and miss shorter windows. The while contracts maximally. And we record right - left + 1 before sum -= nums[left], because that is the instant the window is both valid (sum >= target) and as small as we've made it so far — subtract first and you'd measure an already-shortened or invalid window.
Why this is O(n) despite the nested loop. It looks quadratic, but it isn't: left only ever moves forward and never passes right. Across the entire scan, right increments n times and left increments at most n times. The inner while is bounded by total left movement, not by right's position, so the amortized cost per outer step is O(1) and the whole algorithm is O(n). Stating this amortized argument is what separates a confident answer from a hopeful one.
Why return 0 via an infinity sentinel. Initialise best to infinity. If the array's total never reaches target, best stays infinite and we return 0 per the spec. Using 0 as the initial 'best' would be wrong (0 is a valid minimal length to beat), and returning the sentinel directly would leak ∞/MAX_VALUE.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
target = 7, nums = [2, 3, 1, 2, 4, 3]Array state
right=3
sum=2+3+1+2=8 ≥7 → length 4 candidate
2C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Positivity ⇒ monotonic window sum ⇒ licence to shrink greedily. The expand-right / shrink-left-while-valid template, with the answer recorded at the moment of minimal validity, solves an entire family of shortest/longest-window problems. The amortized 'each index in once, out once' argument is the reusable proof that the nested loop is still linear.
ComplexityO(n) time, O(1) space — `right` advances n times total; `left` advances at most n times total across the whole run. So the combined pointer movement is ≤ 2n → O(n) time. Two integers and a sum → O(1) space.
E · Edge cases and pitfalls8target = 4, nums = [1, 4, 4] — right=1 adds 4 → sum 5 ≥4 → len 2; shrink drops 1 → sum 4 ≥4 → len 1. Answer 1.Explore edge casesHide edge cases
Edge cases handled
target = 4, nums = [1, 4, 4]right=1 adds 4 → sum 5 ≥4 → len 2; shrink drops 1 → sum 4 ≥4 → len 1. Answer 1.target = 11, nums = [1,1,1,1,1,1,1,1]Total 8 < 11, while-loop never enters, best stays ∞ → return 0.target = 6, nums = [10]Single element already ≥ target → len 1.target = 15, nums = [1,2,3,4,5]Whole array sums to 15 exactly → shrinking immediately drops below → answer 5.
Pitfalls
- Using if instead of while to shrink — misses shorter windows when the sum overshoots.
- Recording the length after subtracting nums[left] — measures the wrong window.
- Returning ∞/MAX_VALUE or -1 instead of 0 when nothing qualifies.
- Assuming the technique survives negative values — it doesn't; the sum stops being monotonic.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int minSubArrayLen(int target, int[] nums) { int n = nums.length; int left = 0, sum = 0, best = Integer.MAX_VALUE; for (int right = 0; right < n; right++) { sum += nums[right];Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Using if instead of while to shrink
After adding a large nums[right], several left elements may be removable while still valid. An if removes only one, leaving a longer-than-necessary window and a wrong minimum.
Explore the code comparisonHide the code comparison
Using if instead of while to shrink
After adding a large nums[right], several left elements may be removable while still valid. An if removes only one, leaving a longer-than-necessary window and a wrong minimum.
Don't write this
sum += nums[right];
if (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left];
left++;
}Write this instead
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left];
left++;
}2Recording length after shrinking
Subtracting nums[left] first means you measure a window that may already be invalid or one element too small — the recorded length no longer corresponds to a valid sum.
Explore the code comparisonHide the code comparison
Recording length after shrinking
Subtracting nums[left] first means you measure a window that may already be invalid or one element too small — the recorded length no longer corresponds to a valid sum.
Don't write this
while total >= target:
total -= nums[left]
left += 1
best = min(best, right - left + 1)Write this instead
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 13Returning the sentinel instead of 0
The spec mandates 0 when no subarray qualifies; returning Integer.MAX_VALUE or -1 fails those tests.
Explore the code comparisonHide the code comparison
Returning the sentinel instead of 0
The spec mandates 0 when no subarray qualifies; returning Integer.MAX_VALUE or -1 fails those tests.
Don't write this
return best; // leaks Integer.MAX_VALUE when nothing qualifiedWrite this instead
return best == Integer.MAX_VALUE ? 0 : best;Revise
Carry the pattern into the interview
Pattern to remember
Variable-size sliding window (shrink while valid)
Code pattern to memorize
left = 0; sum = 0; best = ∞
for right in range(n):
sum += nums[right]
while sum >= target: # shrink as much as still valid
best = min(best, right - left + 1)
sum -= nums[left]; left += 1
return 0 if best == ∞ else bestRules to remember
- 1Expand with
right, then shrink withleftusing awhile(notif) so you contract maximally while still>= target. - 2Record the length inside the shrink loop, before removing
nums[left]— that's when the window is minimal-yet-valid. - 3Works because values are positive: adding grows the sum, removing shrinks it — strictly monotonic. Negatives break this.
- 4Each index enters and leaves the window once, so it's O(n) despite the nested loop — amortized analysis.
- 5Return 0 (not −1, not ∞) when no subarray reaches target; initialise
bestto infinity and convert at the end.
Use this pattern when
- Shortest / longest **contiguous** subarray meeting a sum / count threshold
- All values **positive** (or otherwise monotone) so the window sum moves predictably
- A condition that becomes 'satisfied' as the window grows and 'unsatisfied' as it shrinks
- You want O(n) over a brute-force O(n²) range scan
Choose another pattern when
- Array contains **negatives / zeros** → window sum isn't monotonic → use prefix sums + hashing or deque
- **Exact** sum (= k) with negatives → prefix-sum hash map (Subarray Sum Equals K)
- Non-contiguous selection allowed → sorting / heap / DP, not a window
- Need count of all qualifying subarrays, not the min length → different counting technique
Interview takeaway
Positivity makes the window sum monotonic, which is the licence to shrink greedily: expand right, then contract left while still valid, tracking the minimum length. This expand-then-shrink template solves a whole family of 'shortest/longest window with a property' problems in O(n).
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical variable-size Sliding Window: expand right, shrink left while the window stays valid, recording the optimum at the moment of minimal validity. The positivity precondition supplies the monotonicity that licenses the greedy shrink. Same template as Minimum Window Substring and Longest Substring Without Repeating Characters.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Minimum Window SubstringComing soonSame shrink-while-valid window, but validity is a character-count match instead of a sum threshold.
- Longest Substring Without Repeating CharactersComing soonVariable window maximizing length while a 'no duplicates' invariant holds.
- Subarray Sum Equals KComing soonNegatives allowed and exact sum → sliding window fails; use prefix sums + hash map.
- Shortest Subarray with Sum at Least KComing soonSame goal but values may be negative → monotonic deque over prefix sums.