Smallest Subarray with a Given Sum (Variable-Size Sliding Window)

• Variable-size sliding window – the window grows and shrinks dynamically based on a running-sum condition.
• Expand – move the right pointer forward, adding each element to the running sum.
• Shrink – when the sum reaches the target, move the left pointer forward while the sum still meets the target, recording the smallest window length.
• Positivity requirement – all numbers must be positive for the grow/shrink logic to be valid.
• Complexity – O(n) time, O(1) space.

What is the problem?

Given an array of positive numbers and a target sum, find the length of the smallest contiguous subarray whose sum is greater than or equal to the target. If no such subarray exists, return zero.

At the National Bank of India, the treasury team wants to raise at least a target amount of liquidity from a run of consecutive daily deposits using the shortest possible stretch of days.

How does the variable-size sliding window work?

Keep a running sum, a left pointer, and a best length initialized to infinity. Expand the right pointer across the array, adding each element. When the sum reaches the target, shrink from the left.

package com.bank.analytics;

public class SmallestSubarraySum {
    public static int minSubarrayLen(int target, int[] deposits) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

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

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

    public static void main(String[] args) {
        int[] deposits = {2000, 1000, 5000, 2000, 3000, 2000};
        int target = 7000;
        int result = minSubarrayLen(target, deposits);
        System.out.println("Shortest stretch to raise " + target + ": " + result + " days");
    }
}

Shortest stretch to raise 7000: 2 days

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

Although there is a while loop nested inside the for loop, each pointer only moves forward. Across the entire run, the left pointer advances at most n times total. So the inner loop does not multiply the work; the total moves across both pointers is at most 2n.

How is this different from the fixed-size sliding window?

| Variable-Size Window | Fixed-Size Window |
|---|---|
| Window grows and shrinks | Window size is constant k |
| Condition-based shrink | Add-one, subtract-one per slide |
| Finds smallest/longest window | Finds aggregate of fixed-width block |
| Example: min subarray with sum >= target | Example: max sum of size k |

What happens step by step?

For deposits [2000, 1000, 5000, 2000, 3000, 2000] with target 7000:

• right=0: sum=2000. Below target.
• right=1: sum=3000. Below target.
• right=2: sum=8000. Meets target. Length=3. Shrink: sum-2000=6000. left=1. min=3.
• right=3: sum=8000. Meets target. Length=3. Shrink: sum-1000=7000. Length=2. Shrink: sum-5000=2000. left=3. min=2.
• right=4: sum=5000. Below target.
• right=5: sum=7000. Meets target. Length=3. Shrink: sum-2000=5000. left=4. min=2.

Answer: 2 (window [5000, 2000]).

What are the edge cases?

• No valid window: no subarray reaches the target; return 0.
• Single element meets target: a single deposit of 10000 with target 7000; return 1.
• Entire array needed: target equals the total; return the full length.
• Target is zero: every subarray qualifies; the smallest is length 0 or 1 depending on problem definition.

int[] a = {1, 1, 1};
// target = 100: no window reaches it, return 0
// target = 2: window [1,1] has length 2
// target = 3: need all 3 elements, return 3

What are common mistakes?

Forgetting to return zero when no window ever reaches the target.

// Wrong: returns Integer.MAX_VALUE instead of 0
return minLength;

// Correct: check for no-solution
return minLength == Integer.MAX_VALUE ? 0 : minLength;

Another mistake is using if instead of while for the shrink step, which misses the optimal shrink.

// Wrong: shrinks only once per expansion
if (sum >= target) { ... }

// Correct: shrinks as much as possible
while (sum >= target) { ... }

Why do all numbers need to be positive?

With all positive numbers, adding an element always increases the sum and removing one always decreases it. This monotonicity is what makes the grow-and-shrink logic valid. With negative numbers, adding an element could decrease the sum, breaking the shrink invariant.

For arrays with negative numbers, use prefix sums with a monotonic deque or binary search on prefix sums.

What should a senior engineer know?

The O(n) guarantee comes from the amortized analysis: each element is added once (when right advances) and removed at most once (when left advances). The total pointer movements are at most 2n.

This same pattern generalizes to many problems: longest substring with k distinct characters, longest subarray with sum at most target, and any problem where you can define a "valid window" condition that only worsens by expansion and only improves by shrinkage.

What are common interview follow-up questions?

• What if the array contains negative numbers? (Prefix sums + binary search or deque.)
• What if you want the longest subarray with sum at most target? (Same technique, record length when sum is within bounds.)
• What about finding all subarrays that sum to exactly target? (Two-pointer or prefix sum with hash map.)