Minimum Size Subarray Sum

Problem in Plain English

Given an array of positive integers and a target sum, return the smallest length of a contiguous subarray whose elements add up to at least the target, or 0 when no such subarray exists.

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. If there is no such subarray, return 0.

Positivity is the whole trick: extending a window can only raise its sum and shrinking it can only lower it, so test shorter windows by shrinking while the target is still reached, then expand again when the sum falls below it. For target = 7 and nums = [2,3,1,2,4,3] the answer is 2 from [4,3].

Constraints

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

Examples

Example 1

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

The subarray [4,3] sums to 7 with length 2, and no length-1 subarray reaches 7.

Example 2

Input: target = 4, nums = [1,4,4]
Output: 1

The single element [4] reaches the target, so the answer is 1.

Example 3

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

The whole array sums to 8, below 11, so no valid subarray exists.

Example 4

Input: target = 6, nums = [1,2,3]
Output: 3

Only the whole array reaches 6. Removing either endpoint drops the sum below target, so the answer is the full length 3.

Intuition

A valid interval reaches at least target, but we want the shortest one. All numbers are positive: adding a rightmost number raises the sum, and removing a leftmost number lowers it. In Example 1, [2,3,1,2] reaches 8, so record length 4 and remove 2; the remaining sum 6 is too small. Repeating this expand-then-shrink process eventually finds [4,3], sum 7 and length 2.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Every answer is some subarray, so we can test them all directly. From each start we accumulate the sum to the right and stop at the first end reaching target, which is the shortest valid subarray from that start.

Step-by-Step Logic

Initialize best to an unset sentinel. For every start i, initialize sum = 0 and scan end j from i to the array end.
Add nums[j] to sum. When sum >= target, update best with j - i + 1 and stop this start, because every later endpoint produces a longer interval.
In Example 1, start 0 accumulates 2, 5, 6, and 8, then records length 4 at end 3. Start 1 also first qualifies at length 4.
Continue every start: starts 2 and 3 first qualify at length 3; only start 4 qualifies at length 2 with [4,3]. Start 5 never reaches target.
Return 0 if best is still unset, otherwise return best. Example 1 returns 2.

Why It Works

For each start, the first endpoint reaching target is its shortest valid interval. Stopping there cannot miss a shorter interval with that same start, since every later endpoint has greater length. Starts with no qualifying endpoint contribute nothing. Taking the minimum of the shortest valid interval from every possible start therefore finds the global minimum, or returns zero when none exist.

Dry Run

Brute Force: variable states at each step
Start i	End j	Added	Sum after	Length	Action	Best after
0	0	2	2	1	below target: continue	unset
0	1	3	5	2	below target: continue	unset
0	2	1	6	3	below target: continue	unset
0	3	2	8	4	record and break	4
1	1	3	3	1	below target: continue	4
1	2	1	4	2	below target: continue	4
1	3	2	6	3	below target: continue	4
1	4	4	10	4	record and break	4
2	2	1	1	1	below target: continue	4
2	3	2	3	2	below target: continue	4
2	4	4	7	3	record and break	3
3	3	2	2	1	below target: continue	3
3	4	4	6	2	below target: continue	3
3	5	3	9	3	record and break	3
4	4	4	4	1	below target: continue	3
4	5	3	7	2	record and break	2
5	5	3	3	1	below target: continue	2
done	none	none	none	none	return	2

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

If no interval reaches target, the n starts perform n(n + 1)/2 additions, so worst-case time is O(n^2). Early stopping helps some inputs but does not change that bound. Only indices, a running sum, and the minimum sentinel are stored: O(1) auxiliary space. The largest total allowed by n <= 100000 and nums[i] <= 10000 is 1000000000, which fits Java int and exact JavaScript arithmetic.

Code

Solution.java

1class Solution {2    public int minSubArrayLen(int target, int[] nums) {3        int best = Integer.MAX_VALUE;4        for (int i = 0; i < nums.length; i++) {5            int sum = 0;6            for (int j = i; j < nums.length; j++) {7                sum += nums[j];8                if (sum >= target) {9                    if (j - i + 1 < best) {10                        best = j - i + 1;11                    }12                    break;13                }14            }15        }16        return best == Integer.MAX_VALUE ? 0 : best;17    }18}

Hints

Hint 1

Because every element is positive, a window sum grows whenever the window grows and shrinks whenever the window shrinks.

Hint 2

Expand the right edge and keep a running sum; the moment the sum reaches target the window is valid.

Hint 3

A valid window should be shrunk from the left as far as possible before moving right again, since every shrunken-but-valid window is a shorter candidate.

Edge Cases

The total of the whole array stays below target: no window ever validates and the answer is 0.
A single element already reaches target, such as target = 4 with [1,4,4]: the window shrinks to length 1 immediately.
If every element is 1 and target equals n, only the whole array qualifies and the answer is n; target greater than n returns 0.

Common Mistakes and Interview Tips

Shrinking with a single if instead of a while: one expansion can allow several left moves, and the skipped lengths may include the true minimum.
Recomputing the window sum from scratch on each step instead of keeping a running total, which quietly turns the linear scan quadratic.
Returning the unset sentinel instead of 0 when nothing validated, confusing "no window" with a real length.
Subtracting the left value before recording the valid length can lose the shortest qualifying candidate.
Using equality instead of sum >= target misses valid intervals that exceed the target.
Interview tip: state the positive-number assumption. With negative numbers, removing a value can increase the sum, so this monotone window proof no longer applies.

Key Takeaway

For sum goals over positive numbers, expand until valid then shrink while valid: monotonic sums make one pass enough for the shortest window.