Coding · Sliding window
Minimum Size Subarray Sum
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
Given an array of positive integers and a positive target, return the length of the shortest contiguous run of elements whose sum is at least the target, or 0 if no run is big enough. For target 7 and [2,3,1,2,4,3] the answer is 2, from the run [4,3]. The array can hold 100,000 numbers, so checking every pair of ends is too slow.
Restated in our own words, not a quote from Zomato or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are all numbers strictly positive, or can there be zeros or negatives? Is the target always positive? Do I need a contiguous run, or any subset? Is the requirement a sum of at least the target, or exactly the target? What do I return for an empty array, or when even the whole array falls short? How long can the array be, and could the sum overflow?
I would assume positive integers, a positive target, a contiguous run with sum at least the target, a result of 0 when none exists, and a total that fits in a normal JavaScript number.
Brute force
Say the obvious answer and why it is too slow.
Try every start. For each start, add elements one at a time until the sum reaches the target, record the length, and move to the next start. Stopping at the first success keeps each start cheap in a lucky case, but when the target is large or unreachable every start scans to the end. That is O(n²) time. Recomputing each sum from scratch instead of keeping a running total would make it O(n³).
With 100,000 numbers, n² is about ten billion steps, far past what runs in a second. The waste is that the sums of neighboring runs share almost every element, yet this approach rebuilds each one from nothing.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(1) extra
The pattern is a variable-size sliding window. Keep a window from left to right and its running sum. Move right one step at a time, adding the new number. While the sum is at least the target, the window is a valid answer: record its length, then drop the leftmost number and move left forward to see whether a shorter window still works.
Why this finds the true minimum: fix an end position. The best start for it is the largest left whose sum still reaches the target. Because every number is positive, making the window longer on the right only raises its sum, so a start that was good for one end is still good for the next end. That means the best start never moves backward as the end moves forward, and left only ever advances. No candidate is skipped, because every shrink step happens only after the valid window was measured.
Each index is added once and removed at most once, so the work is O(n) even though the loop is nested. Only a few numbers are stored, so extra space is O(1). The positivity is doing real work: with negatives, dropping a number can raise the sum, and the argument above breaks. I would say it out loud as: grow until it is enough, then shrink while it is still enough, and remember the shortest size seen.
Walk it through
A dry run on the example, step by step.
| right | Sum after adding | Lengths recorded | left at end | Best so far |
|---|---|---|---|---|
| 0 | 2 | none | 0 | none |
| 1 | 5 | none | 0 | none |
| 2 | 6 | none | 0 | none |
| 3 | 8 | 4 | 1 | 4 |
| 4 | 10 | 4, 3 | 3 | 3 |
| 5 | 9 | 3, 2 | 5 | 2 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Use target 7 on [2,3,1,2,4,3]. The trace shows the state after each right step. For right = 0, 1 and 2 the sums are 2, 5 and 6, all below 7, so nothing is recorded. At right = 3 the sum is 8, which is enough: record length 4, drop the 2, and the sum falls to 6, below the target.
At right = 4 the sum is 10. Record length 4 for [3,1,2,4], drop the 3 to get 7, which still works, so record length 3 for [1,2,4], drop the 1 and stop at 6. At right = 5 the sum is 9: record 3, drop the 2 to get 7, record 2 for [4,3], drop the 4 to get 3 and stop. The best length seen is 2.
The code
Runnable JavaScript, checked against test cases.
function minSubArrayLen(target, nums) {
let left = 0;
let windowSum = 0;
let shortest = Infinity;
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right];
while (windowSum >= target) {
shortest = Math.min(shortest, right - left + 1);
windowSum -= nums[left];
left++;
}
}
return shortest === Infinity ? 0 : shortest;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty array: the loop never runs and the shortest length stays at Infinity, so the function returns 0. Total sum below the target: the inner loop never fires, same result of 0. A single number at least as big as the target: the window of length 1 is recorded at once, and the answer is 1, the smallest possible. The whole array needed: the window only reaches the target on the last step, so the answer is n.
Target met exactly: the test is greater than or equal, so a sum equal to the target counts. A big number followed by small ones: the shrinking loop may run several times in one step, which is why it must be a while loop and not a single if. Infinity is turned into 0 only at the return, so no real length is confused with the missing case.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it if the array could contain negative numbers?
- How would you also return the start and end index of the shortest run?
- Could you solve it with prefix sums and binary search, and what would that cost?
- What changes if the sum must equal the target exactly instead of reaching it?
- How would you count the runs whose sum is at least the target?
Where candidates slip
The mistakes this problem punishes.
The most common slip is writing if instead of while for the shrinking step. After one drop the window may still be valid, and a single drop leaves shorter answers undiscovered. The second is recording the length after shrinking instead of before, which measures a window that no longer reaches the target.
Others: returning Infinity (or n + 1) when no window exists instead of 0; computing the length as right - left without the + 1; resetting left to 0 on every right; and using this approach when the array may contain negatives, where the window argument fails and prefix sums with a monotonic deque are needed. Some people also reach for sorting first, which destroys the contiguity the problem depends on.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.