Minimum Size Subarray Sum >= Target: Variable Window, Shrink When Satisfied

• Minimum size subarray sum – finds the length of the shortest contiguous subarray whose sum >= target, over positive numbers.
• Variable-size window – the right edge expands to grow the sum; when the sum meets the target, the left edge shrinks as far as possible while still qualifying.
• Shortest-valid pattern – shrink while the window is valid and record the width before each shrink.
• O(n) time, O(1) space – each element is added once and removed once; the left pointer only advances.
• Positivity required – all values must be positive for the greedy shrink to be correct.

What is the Minimum Size Subarray Sum problem?

Given an array of positive integers and a target sum, find the length of the shortest contiguous subarray whose sum is at least the target. Return 0 if no such subarray exists.

At the National Bank of India, the loan desk computes the fewest consecutive days in which Rajesh accumulated at least the required down payment as evidence of saving discipline.

How does the variable-size sliding window work?

Maintain left = 0, a running sum = 0, and best = Integer.MAX_VALUE. In an outer loop, advance right and add a[right] to the sum. Then, in an inner while loop that runs while sum >= target, record the window width if it is smaller than best, subtract a[left], and advance left.

Array: [2, 3, 1, 2, 4, 3]   target = 7

right=0: sum=2
right=1: sum=5
right=2: sum=6
right=3: sum=8 >= 7 → width=4, shrink: sum=6, left=1
right=4: sum=10 >= 7 → width=4, shrink: sum=7 >= 7 → width=3, shrink: sum=6, left=3
right=5: sum=9 >= 7 → width=3, shrink: sum=7 >= 7 → width=2, shrink: sum=3, left=5

Answer: 2 (subarray [4, 3])

How do you implement it? (with code)

package com.bank.loan;

import java.math.BigDecimal;

public class MinSizeSubarraySum {

    public static int minSubarrayLen(BigDecimal[] deposits, BigDecimal target) {
        int left = 0;
        int best = Integer.MAX_VALUE;
        BigDecimal sum = BigDecimal.ZERO;

        for (int right = 0; right < deposits.length; right++) {
            sum = sum.add(deposits[right]);

            while (sum.compareTo(target) >= 0) {
                int width = right - left + 1;
                if (width < best) {
                    best = width;
                }
                sum = sum.subtract(deposits[left]);
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    public static void main(String[] args) {
        BigDecimal[] deposits = {
            new BigDecimal("200"), new BigDecimal("300"),
            new BigDecimal("100"), new BigDecimal("200"),
            new BigDecimal("400"), new BigDecimal("300")
        };
        BigDecimal target = new BigDecimal("700");
        int result = minSubarrayLen(deposits, target);
        System.out.println("Minimum days to reach " + target + ": " + result);
    }
}

Minimum days to reach 700: 2

What is the shortest-valid vs longest-valid distinction?

This is a critical pattern distinction in sliding window problems.

| Pattern | Shrink condition | Record when | Example problem |
|---|---|---|---|
| Shortest-valid | Shrink while window IS valid | Before each shrink | Min size subarray sum |
| Longest-valid | Shrink while window is INVALID | After shrinking | Longest substring without repeats |

For shortest-valid, you shrink while the condition holds and record the width before each shrink, so you capture the tightest qualifying window at each right position.

Why must all values be positive?

Positive values guarantee that the sum increases as the window grows and decreases as it shrinks. This monotonic behavior makes the greedy shrink correct: once the sum drops below the target after shrinking, extending the left edge further would only make it worse.

With negatives, adding an element might decrease the sum, and removing one might increase it, so the monotonic assumption breaks. You would need a prefix-sum with a deque or a different approach.

Why is the time complexity O(n) despite the nested loop?

The left pointer only advances and never resets. Each element is added to the sum exactly once (when right reaches it) and removed from the sum at most once (when left passes it). So the total work across all iterations of both loops is at most 2n, which is O(n).

What are the edge cases?

• No subarray reaches target – return 0 (the sentinel Integer.MAX_VALUE is never updated).
• Single element equals target – return 1.
• Entire array sums to less than target – return 0.
• First element alone exceeds target – return 1.

How is this different from the fixed-size window?

| Aspect | Fixed-size (K) | Variable-size (min length) |
|---|---|---|
| Window width | Always K | Varies |
| Slide rule | Add right, subtract left simultaneously | Grow right, then shrink left |
| Optimization target | Maximum sum of fixed width | Minimum width meeting a sum threshold |

What are common interview follow-up questions?

- **What if negatives are allowed?** – Use prefix sums with a deque for O(n), or O(n log n) with binary search on prefix sums.
- **What about the longest subarray with sum <= target?** – Same window, but this is a longest-valid pattern.
- **Can you return the actual subarray?** – Track bestLeft and bestRight when best is updated.