minimum-size-subarray-sum

Difficulty: Easy  ·  Topic: Sliding Window  ·  Practice it on parikshan: /practice/minimum-size-subarray-sum/start

The story

You are on Stripe's billing infrastructure team. A merchant uploads a CSV of daily revenues and asks: "What is the shortest stretch of consecutive days during which I crossed my quarterly target of $50,000 in cumulative sales?" The merchant wants to know how fast a hot streak can hit a target. They send you the daily numbers (always positive) and the target. You return the minimum number of consecutive days whose sum reached or exceeded the target, or 0 if no such stretch exists.

That is minimum-size-subarray-sum. Generalised: shortest contiguous subarray with sum at least target, in a positive-integer array.

What's actually being asked

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

The positive integers constraint is critical. It is what makes the sliding-window approach valid: adding an element can only increase the sum, and removing one can only decrease it. With negative numbers allowed, this monotonicity breaks and you need a different technique (prefix sums with a monotonic deque, or binary search on prefix sums).

The naive approach

Two nested loops. For every i, expand j until the sum reaches target, record j - i + 1. O(n^2). For n = 5 * 10^4, that is 2.5 billion. Times out.

The key insight

A variable-size sliding window where left and right both move forward, never backward. Maintain cur = sum of the window.

• Walk right forward, adding nums[right] to cur.
• While cur >= target, the current window is valid: record right - left + 1 as a candidate length, then shrink by subtracting nums[left] and advancing left. (You shrink while valid because a smaller valid window is what you want; you stop shrinking the moment validity is lost.)

Because both pointers only move forward, each element is added and removed at most once: O(n).

The shrink condition is while, not if. After adding a large new element, the window might be valid with multiple-element shrinks; shrinking one position would miss the optimum.

Step-by-step approach

1. left = 0, cur = 0, best = infinity.
2. For right from 0 to n - 1:
   • cur += nums[right].
   • While cur >= target:
     • best = min(best, right - left + 1).
     • cur -= nums[left].
     • left += 1.
3. If best is still infinity, return 0. Else return best.

Worked example

nums = [2, 3, 1, 2, 4, 3], target = 7

Let me redo the last row carefully:

• right=5, cur=6+3=9. Enter inner loop.
• cur=9 >= 7. best = min(3, 5-3+1) = min(3, 3) = 3. cur = 9 - nums[3] = 9 - 2 = 7. left=4.
• cur=7 >= 7. best = min(3, 5-4+1) = min(3, 2) = 2. cur = 7 - nums[4] = 7 - 4 = 3. left=5.
• cur=3 < 7. Exit.

Answer: 2 (subarray [4, 3] at indices 4, 5).

Complexity

• Time: O(n). Each index enters and leaves the window at most once.
• Space: O(1).

The brute force is O(n^2). The sliding-window approach drops to O(n) because of the monotonicity of partial sums on positive inputs.

Common pitfalls

• Returning the smallest window without checking it exists: if no window meets the target, best stays at infinity, return 0.
• Using <= target instead of >= target: read the spec; the constraint is "sum is at least target", not "exactly target".
• Recording best after the shrink instead of inside the while-loop: you would record the first invalid window, not the smallest valid one.
• Shrinking with if instead of while: misses the case where multiple positions need to be shrunk.
• Trying to apply this to arrays with negatives: the algorithm is wrong on negative inputs. Use prefix sums and a monotonic deque, or sort-and-search.

Where this shows up in the enterprise

• Stripe / Square / Adyen merchant dashboards: shortest streak to hit a payout threshold.
• Cloud cost management (AWS Cost Explorer, GCP Billing): shortest billing window where spend exceeded budget.
• Salesforce / HubSpot sales pipelines: shortest period where pipeline value crossed a quota.
• GitHub repository insights: shortest commit-streak where lines added crossed a refactor threshold.
• Strava / Garmin training plans: shortest workout segment crossing a calorie target.
• Robinhood / Coinbase: shortest trading window where cumulative volume hit a regulatory threshold.
• Splunk / Elastic SIEM: shortest alert window where cumulative severity score exceeded an escalation trigger.
• Performance budgets at Cloudflare / Vercel: shortest deployment window where cumulative error budget was burned.

The shape: "what is the shortest stretch where a positive accumulator exceeded a threshold?" Everywhere.

Variants you'll see elsewhere

• subarray-sum-equals-k: count subarrays with sum exactly k; prefix sum + hash map, not sliding window (because k can be hit non-monotonically with zero or negative numbers).
• maximum-size-subarray-sum-equals-k: longest subarray with sum exactly k. Hash-map of prefix sums.
• shortest-subarray-with-sum-at-least-k: same problem but allowing negatives, much harder; monotonic deque on prefix sums.
• longest-subarray-with-sum-at-most-k: dual; same sliding-window pattern with positive numbers.
• binary-subarrays-with-sum: count, not length.

How parikshan turns this into a learning loop

The parikshan dynamic private tests on this problem cover:

• target = 1 (any element >= 1, so length 1; tests that you record the answer immediately).
• target larger than the sum of all elements (no valid window, return 0).
• The whole array sums to exactly target (return n).
• A single huge element exceeding target on its own.
• A pathological array where the shrink fires many times in one iteration.

If your code fails the "no valid window" test by returning a stale best value, you forgot the infinity sentinel. If it fails the "shrink many times" test, you wrote if instead of while. Each failure points at exactly one line of code; the dynamic tests do the debugging instruction for you.

In the AI-integrated workspace

When an agent writes a "shortest streak above threshold" function, your review:

1. Does it use two pointers, both forward-only? If the agent restarts left from i+1 on each outer iteration, that is the O(n^2) brute force in disguise.
2. Is the inner shrink a while, not an if?
3. Is best initialised to infinity (or n + 1, or any sentinel above n)? And is 0 returned when nothing is found?
4. Is the input guaranteed to be positive? If not, the agent must use prefix sums and a deque, not this algorithm. This is the most common silent bug: the agent generates the sliding-window code for an input that might include negatives, and the function silently returns wrong answers.

The fourth check is the one a senior engineer must internalise. Sliding windows on sums require monotonicity (all positive or all negative). The moment that assumption breaks, the algorithm is invalid. parikshan trains the recognition by giving you the positive-only version here, then the deque version in a harder cluster later.