DSA-026 · Positive-sum threshold window

Minimum Size Subarray Sum — Positive Inputs

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 5476 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the minimum length of a contiguous subarray whose sum is at least target, under a strictly positive-input contract.

nums is non-null with 0–100,000 positive int entries, each 1..Integer.MAX_VALUE. target is a positive long up to Long.MAX_VALUE. Both methods throw IllegalArgumentException for target≤0 or any value≤0; null is outside the contract.
Return the shortest qualifying nonempty length, or 0 when none exists. Empty input therefore returns 0 for a valid target. Preserve nums.
Use long sums. The greatest full-array sum under these bounds is below Long.MAX_VALUE. Negative or zero values are rejected explicitly; the monotonic proof below depends on positivity.

Examples

Input: target=7, nums=[2,3,1,2,4,3]
Output: 2
The final [4,3] reaches seven in two positions.
Input: target=4294967294, nums=[2147483647,2147483647]
Output: 2
The sum exceeds int range but is exact as long.

Before you start

Contiguous windows, inclusive bounds, and empty intervals
Java frequency arrays and loop-invariant reasoning

Recognize the structure

Positivity makes adding a value increase the window sum and removing one decrease it. Once a window qualifies, shrink it to explore shorter qualifying suffixes without revisiting earlier starts.

Try before revealing

Hint 1

What does strict positivity guarantee about removing the left endpoint?

Hint 2

When a window qualifies, can its shorter suffix still qualify?

Hint 3

Record each valid length and shrink until the sum drops below target.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate each start with a running sum

For each start, extend until the sum first reaches target, then stop that start. With [2,3,1,2] and target 6, start 0 first qualifies as [2,3,1] of length three; start 1 qualifies as [3,1,2], also length three. Later endpoints for the same start are longer, so cannot help. This costs O(n²) time and O(1) space.

Improve the baseline

Maintain an exact long sum

Add nums[right] and keep sum equal to the retained contiguous interval. A positive target means an empty interval never qualifies.

Record then shrink

While sum≥target, update best from right-left+1 and remove nums[left]. A single removal may leave coverage valid, so use while rather than if.

Never revisit a discarded start

A discarded start already produced a qualifying window; any later endpoint with that start is longer. If no best was recorded, return the sentinel result zero.

Why it is correct

State invariant

sum is exactly the mathematical sum of nums[left..right] and best is the smallest recorded qualifying length. Long arithmetic is sufficient under the n and int-value bounds.

Safe contraction and expansion

Each qualifying candidate is recorded before removing its left value. Positivity means each removal decreases sum until the shortest qualifying suffix is passed. Earlier discarded starts cannot improve with a later right because their windows would be longer.

Global minimum

Any candidate with an unprocessed start is examined once its sum reaches target; discarded starts already have no worse earlier candidates. The best recorded length is thus optimal. Each pointer advances at most n times, and validation adds only one linear scan.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    private static void validate(long target, int[] nums) {
        if (target <= 0) throw new IllegalArgumentException("target must be positive");
        for (int value : nums) if (value <= 0) throw new IllegalArgumentException("values must be positive");
    }
    public static int minSubArrayLen(long target, int[] nums) {
        validate(target, nums);
        int left = 0, best = Integer.MAX_VALUE;
        long sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= nums[left++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
    public static int baseline(long target, int[] nums) {
        validate(target, nums);
        int best = Integer.MAX_VALUE;
        for (int start = 0; start < nums.length; start++) {
            long sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum >= target) { best = Math.min(best, end - start + 1); break; }
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

Read the meaningful blocks

Validate before scanning

Reject zero or negative values and nonpositive targets consistently in both optimized and baseline methods.

Long sum from the start

Assigning an int overflow into a long variable would not repair it. Here each addition is into an already-long accumulator.

Use a real absence sentinel

best starts at Integer.MAX_VALUE; convert it to zero only on return. Zero is not an initial candidate minimum.

Complexity

O(n) time including validation, one right scan and at most n total left removals. O(1) auxiliary space; input is preserved.

The running-sum baseline is O(n²) time and O(1) space. Tests use BigInteger sums on small cases and a closed-form large boundary case, so wide arithmetic is checked independently.

Exact-state walkthroughs

Reveal normal and boundary traces

Shrink several qualifying suffixes

Input: {"target":7,"nums":[2,3,1,2,4,3]} · Result: 2

Step 1 of 18: Validate the input and initialize the empty interval.

The declared value domain makes the window cost monotone under expansion.

Original input — highlighted current interval

0: 2
1: 3
2: 1
3: 2
4: 4
5: 3

Current sum: 0. Target: 7. Every qualifying length is considered before its left value is removed.

State after this step
Variable	Value
values	`[2,3,1,2,4,3]`
left	`0`
right	`-1`
sum	`0`
target	`7`
best	`null`

See the affected Java block

 1 public final class Solution {
 2     private static void validate(long target, int[] nums) {
 3         if (target <= 0) throw new IllegalArgumentException("target must be positive");
 4         for (int value : nums) if (value <= 0) throw new IllegalArgumentException("values must be positive");
 5     }
 6     public static int minSubArrayLen(long target, int[] nums) {
 7         validate(target, nums);
 8         int left = 0, best = Integer.MAX_VALUE;
 9         long sum = 0;
10         for (int right = 0; right < nums.length; right++) {
11             sum += nums[right];
12             while (sum >= target) {
13                 best = Math.min(best, right - left + 1);
14                 sum -= nums[left++];
15             }
16         }
17         return best == Integer.MAX_VALUE ? 0 : best;
18     }
19     public static int baseline(long target, int[] nums) {
20         validate(target, nums);
21         int best = Integer.MAX_VALUE;
22         for (int start = 0; start < nums.length; start++) {
23             long sum = 0;
24             for (int end = start; end < nums.length; end++) {
25                 sum += nums[end];
26                 if (sum >= target) { best = Math.min(best, end - start + 1); break; }
27             }
28         }
29         return best == Integer.MAX_VALUE ? 0 : best;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the input and initialize the empty interval.
The declared value domain makes the window cost monotone under expansion.
values
[2,3,1,2,4,3]
left
0
right
-1
sum
0
target
7
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[2,3,1,2,4,3]
left
0
right
0
sum
2
target
7
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[2,3,1,2,4,3]
left
0
right
1
sum
5
target
7
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[2,3,1,2,4,3]
left
0
right
2
sum
6
target
7
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[2,3,1,2,4,3]
left
0
right
3
sum
8
target
7
best
null
Record a qualifying length before contraction.
This candidate is nonempty and reaches the target; later windows with the same start would be longer.
values
[2,3,1,2,4,3]
left
0
right
3
sum
8
target
7
best
4
Remove the positive left value.
The sum decreases, and another qualifying suffix must still be considered.
values
[2,3,1,2,4,3]
left
1
right
3
sum
6
target
7
best
4
outgoing
2
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[2,3,1,2,4,3]
left
1
right
4
sum
10
target
7
best
4
Record a qualifying length before contraction.
This candidate is nonempty and reaches the target; later windows with the same start would be longer.
values
[2,3,1,2,4,3]
left
1
right
4
sum
10
target
7
best
4
Remove the positive left value.
The sum decreases, and another qualifying suffix must still be considered.
values
[2,3,1,2,4,3]
left
2
right
4
sum
7
target
7
best
4
outgoing
3
Record a qualifying length before contraction.
This candidate is nonempty and reaches the target; later windows with the same start would be longer.
values
[2,3,1,2,4,3]
left
2
right
4
sum
7
target
7
best
3
Remove the positive left value.
The sum decreases, and another qualifying suffix must still be considered.
values
[2,3,1,2,4,3]
left
3
right
4
sum
6
target
7
best
3
outgoing
1
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[2,3,1,2,4,3]
left
3
right
5
sum
9
target
7
best
3
Record a qualifying length before contraction.
This candidate is nonempty and reaches the target; later windows with the same start would be longer.
values
[2,3,1,2,4,3]
left
3
right
5
sum
9
target
7
best
3
Remove the positive left value.
The sum decreases, and another qualifying suffix must still be considered.
values
[2,3,1,2,4,3]
left
4
right
5
sum
7
target
7
best
3
outgoing
2
Record a qualifying length before contraction.
This candidate is nonempty and reaches the target; later windows with the same start would be longer.
values
[2,3,1,2,4,3]
left
4
right
5
sum
7
target
7
best
2
Remove the positive left value.
The sum decreases, and another qualifying suffix must still be considered.
values
[2,3,1,2,4,3]
left
5
right
5
sum
3
target
7
best
2
outgoing
4
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
2

No subarray reaches the threshold

Input: {"target":8,"nums":[1,2,3]} · Result: 0

Step 1 of 5: Validate the input and initialize the empty interval.

The declared value domain makes the window cost monotone under expansion.

Original input — highlighted current interval

0: 1
1: 2
2: 3

Current sum: 0. Target: 8. Every qualifying length is considered before its left value is removed.

State after this step
Variable	Value
values	`[1,2,3]`
left	`0`
right	`-1`
sum	`0`
target	`8`
best	`null`

See the affected Java block

 1 public final class Solution {
 2     private static void validate(long target, int[] nums) {
 3         if (target <= 0) throw new IllegalArgumentException("target must be positive");
 4         for (int value : nums) if (value <= 0) throw new IllegalArgumentException("values must be positive");
 5     }
 6     public static int minSubArrayLen(long target, int[] nums) {
 7         validate(target, nums);
 8         int left = 0, best = Integer.MAX_VALUE;
 9         long sum = 0;
10         for (int right = 0; right < nums.length; right++) {
11             sum += nums[right];
12             while (sum >= target) {
13                 best = Math.min(best, right - left + 1);
14                 sum -= nums[left++];
15             }
16         }
17         return best == Integer.MAX_VALUE ? 0 : best;
18     }
19     public static int baseline(long target, int[] nums) {
20         validate(target, nums);
21         int best = Integer.MAX_VALUE;
22         for (int start = 0; start < nums.length; start++) {
23             long sum = 0;
24             for (int end = start; end < nums.length; end++) {
25                 sum += nums[end];
26                 if (sum >= target) { best = Math.min(best, end - start + 1); break; }
27             }
28         }
29         return best == Integer.MAX_VALUE ? 0 : best;
30     }
31 }
32

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate the input and initialize the empty interval.
The declared value domain makes the window cost monotone under expansion.
values
[1,2,3]
left
0
right
-1
sum
0
target
8
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,2,3]
left
0
right
0
sum
1
target
8
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,2,3]
left
0
right
1
sum
3
target
8
best
null
Include the next input occurrence.
The running sum or zero count describes exactly the current interval.
values
[1,2,3]
left
0
right
2
sum
6
target
8
best
null
Return the contract result.
The result follows the declared empty, ordering, tie, and mutation rules.
result
0

Test the contract

Input: target=5, nums=[]
Output: 0
No nonempty candidate.
Input: target=10, nums=[1,1,10]
Output: 1
Repeated shrinking is necessary.
Input: target=8, nums=[1,2,3]
Output: 0
No feasible sum.
Input: target=1, nums=[0,1]
Output: IllegalArgumentException
Zero violates the explicit strict-positivity rule.

Common mistakes and counterexamples

Apply this to arbitrary negatives

Counterexample: With [1,-1,5],target 5 the normal window records length three and can stop shrinking after removing 1, missing the optimal [5].

Reject negatives here; use prefix sums with a monotonic deque for the general shortest-threshold problem.

Shrink only once

Counterexample: [1,1,10],target 10 must shrink repeatedly to find length one.

Use while sum≥target.

Initialize best to zero

Counterexample: Math.min(0,positiveLength) never improves.

Use an absence sentinel and map it to zero on return.

Follow-ups

Allow negative values.

Use prefix sums P and find the shortest j-i with P[j]-P[i]≥target. A monotonic deque of candidate prefix indices supports safe dominance and threshold removals; ordinary positive-window contraction is insufficient.

Allow zero values.

For positive target, nonnegative values still allow the shrink template, though removals may keep the same sum. This API deliberately rejects zeros; revise validation, proof wording, and tests together before broadening it.

Count subarrays with an exact sum.

This is a different output objective. With arbitrary signed values, a prefix-sum frequency map counts earlier prefixes equal to currentSum-target; one minimal window cannot represent all matching intervals.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 101/20,000 characters

Self-review

I state and validate positivity.I prove why discarded starts are safe.I use long arithmetic and an honest absence value.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Sliding windows: define validity first

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.