Minimum Size Subarray Sum (Shortest Subarray with Sum At Least Target)

• This problem asks for the smallest length of a contiguous subarray whose sum is at least a target.
• All elements are positive, which makes the running sum monotonically increase as the window grows.
• A variable-size sliding window grows right and shrinks left aggressively while the sum qualifies.
• The shrink-while-valid pattern finds the shortest qualifying window ending at each position.
• Time is O(N) and space is O(1).
• If negatives are present, a prefix-sum plus monotonic deque is required instead.

What is the Minimum Size Subarray Sum problem?

Given an array of positive integers and a target value, find the length of the shortest contiguous subarray whose sum is greater than or equal to the target. Return 0 if no such subarray exists. This is LeetCode 209.

For example, given [2, 3, 1, 2, 4, 3] and target = 7, the shortest qualifying subarray is [4, 3] with length 2.

How does the sliding window work?

We maintain a window with left and right boundaries and a running sum. The right pointer moves forward, adding elements. After each addition, we shrink from the left while the sum stays at or above the target, recording the shortest qualifying window.

package com.bank.service;

public class MinSubarraySumService {

    /**
     * Finds the fewest consecutive days to reach a liquidity target.
     * Used by the National Bank of India treasury team.
     */
    public static int minSubarrayLen(int target, int[] deposits) {
        int left = 0;
        long sum = 0;
        int best = Integer.MAX_VALUE;

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

            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= deposits[left];
                left++;
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    public static void main(String[] args) {
        int[] deposits = {20000, 30000, 10000, 20000, 40000, 30000};
        int target = 70000;
        int days = minSubarrayLen(target, deposits);
        System.out.println("Fewest days to reach Rs." + target + ": " + days);
    }
}

javac -d out com/bank/service/MinSubarraySumService.java
java -cp out com.bank.service.MinSubarraySumService

Fewest days to reach Rs.70000: 2

Why does the greedy shrink work only with positive numbers?

Because every element is positive, adding an element strictly increases the sum and removing an element strictly decreases it. This monotonic behavior lets us greedily shrink from the left without missing a shorter answer. The moment the sum drops below the target, we know no further shrinking will help, so we expand right again.

If the array contained negatives, removing an element could increase the sum, breaking the monotonicity and making the greedy shrink incorrect.

// WORKS: all positive, sum is monotonic
int[] positive = {2, 3, 1, 2, 4, 3}; // greedy shrink is safe

// BREAKS: negatives present, sum is not monotonic
int[] mixed = {2, -1, 5, -2, 3}; // shrinking left might increase sum
// Need prefix-sum + monotonic deque for this case

What happens when no subarray qualifies?

If the total sum of the entire array is less than the target, no window ever qualifies. We detect this because the best variable remains at its sentinel value Integer.MAX_VALUE, and we return 0.

What are the edge cases?

Several edge cases require attention.

• Single element >= target: the answer is 1.
• All elements together < target: the answer is 0.
• All elements equal: the answer is ceil(target / element).
• Target is zero: every non-empty subarray qualifies, so the answer is 1 (or 0 if we require a positive sum).

package com.bank.core;

public class MinSubarrayEdgeCases {
    public static void main(String[] args) {
        // Single large deposit
        System.out.println(minSubarrayLen(50000, new int[]{100000})); // 1

        // Total too small
        System.out.println(minSubarrayLen(100000, new int[]{1000, 2000})); // 0

        // All equal
        System.out.println(minSubarrayLen(30000, new int[]{10000, 10000, 10000, 10000})); // 3
    }

    static int minSubarrayLen(int target, int[] arr) {
        int left = 0, best = Integer.MAX_VALUE; long sum = 0;
        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];
            while (sum >= target) { best = Math.min(best, right - left + 1); sum -= arr[left++]; }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

1
0
3

What is the time and space complexity?

Time is O(N) because the right pointer advances N times and the left pointer only moves forward. Together they take at most 2N steps. Space is O(1): a running sum and a few index variables.

How does this compare to the negative-numbers variant?

When the array can contain negatives, the simple shrink window fails. You need a prefix-sum array and a monotonic deque (see Q1707: Shortest Subarray with Sum at Least K). That algorithm is O(N) but significantly more complex.

| Variant | Elements | Algorithm | Time |
|---|---|---|---|
| Positive only | All positive | Sliding window | O(N) |
| With negatives | Mixed signs | Prefix sum + deque | O(N) |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Shrink-aggressively vs grow-aggressively: this problem shrinks aggressively (minimize window), while the longest-subarray problems grow aggressively (maximize window). Knowing which direction to be greedy in is the real skill.
• Overflow: for monetary data, accumulate the sum in a long to prevent integer overflow on long sequences.
• Binary search alternative: build a prefix-sum array and, for each right endpoint, binary search for the leftmost left endpoint. This is O(N log N) and demonstrates a different technique.
• Production context: for corporate accounts, daily inflows can be large. Using long or BigDecimal is essential.

What are common interview follow-up questions?

Interviewers often extend this problem.

• Shortest Subarray with Sum at Least K (with negatives): requires prefix-sum plus monotonic deque.
• Maximum size subarray sum equals K: requires prefix-sum with a hash map.
• Minimum window substring: the string analog with character frequency counting.