Minimum Size Subarray Sum: Sliding Window in Six Languages

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

Examples

Input	Output	Why
`nums = [2, 3, 1, 2, 4, 3], target = 7`	`2`	The subarray [4, 3] sums to 7 and nothing shorter reaches it.
`nums = [1, 1, 1, 1, 1, 1, 1, 1], target = 11`	`0`	The whole array sums to 8.
`nums = [1, 4, 4], target = 4`	`1`	A single element is enough.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ nums[i] ≤ 10⁴
1 ≤ target ≤ 10⁹
Every value is strictly positive

Hints

Hint 1

There are n(n+1)/2 subarrays. Enumerating them is O(n²) even with a running sum. What property of the input lets you skip most of them?

Hint 2

Every value is positive, so extending a window can only increase its sum and shrinking it can only decrease it. The sum is monotone in the window.

Hint 3

Grow the right end until the window qualifies. Then, before growing again, shrink from the left for as long as it still qualifies — each shrink gives a shorter candidate.

Where people lose marks

Returning the running best as 0 when nothing qualifies, but initialising best to 0 as well — then a real answer of, say, 3 never replaces it. Initialise to n + 1 or to infinity and convert at the end.
Shrinking with while (sum > target) rather than >=, which stops one step early and returns a length one too long.
Summing into a 32-bit integer. With n = 10⁵ and values up to 10⁴ the total reaches 10⁹, which is close enough to the limit to be worth a 64-bit accumulator.
Reaching for prefix sums and binary search, O(n log n). It is a correct answer to a question that has an O(n) one.

Dry run on `[2,3,1,2,4,3],7`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 12

Step 1 / 12

nums
20lo/hi3112234435
sum2target7best—
Add nums[0] = 2. The window is [0, 0] and sums to 2, still short of 7.
Step 2 / 12

nums
20lo31hi12234435
sum5target7best—
Add nums[1] = 3. The window is [0, 1] and sums to 5, still short of 7.
Step 3 / 12

nums
20lo3112hi234435
sum6target7best—
Add nums[2] = 1. The window is [0, 2] and sums to 6, still short of 7.
Step 4 / 12

nums
20lo311223hi4435
sum8target7best—
Add nums[3] = 2. The window is [0, 3] and sums to 8, which reaches the target.
Step 5 / 12

nums
20lo311223hi4435
sum8target7best4
Sum 8 ≥ 7, so length 4 is a candidate. Drop nums[0] = 2 and see whether it still qualifies.
Step 6 / 12

nums
2031lo122344hi35
sum10target7best4
Add nums[4] = 4. The window is [1, 4] and sums to 10, which reaches the target.
Step 7 / 12

nums
2031lo122344hi35
sum10target7best4
Sum 10 ≥ 7, so length 4 is a candidate. Drop nums[1] = 3 and see whether it still qualifies.
Step 8 / 12

nums
203112lo2344hi35
sum7target7best3
Sum 7 ≥ 7, so length 3 is a candidate. Drop nums[2] = 1 and see whether it still qualifies.
Step 9 / 12

nums
20311223lo4435hi
sum9target7best3
Add nums[5] = 3. The window is [3, 5] and sums to 9, which reaches the target.
Step 10 / 12

nums
20311223lo4435hi
sum9target7best3
Sum 9 ≥ 7, so length 3 is a candidate. Drop nums[3] = 2 and see whether it still qualifies.
Step 11 / 12

nums
2031122344lo35hi
sum7target7best2
Sum 7 ≥ 7, so length 2 is a candidate. Drop nums[4] = 4 and see whether it still qualifies.
Step 12 / 12

nums
203112234435
answer2
Nothing shorter than 2 ever qualified. Return 2.

How to think about it

The constraint that carries this problem is all values are positive. It means the window sum moves in one direction as each end moves, so you never have to reconsider a position you have passed.

Keep a window [lo, hi] and a running sum. Move hi right one step at a time, adding as you go. The moment the sum reaches the target, the window is a valid answer — but probably not the shortest one ending at hi. So shrink: while the sum is still at least the target, record the length and move lo right, subtracting as you go.

Each index enters the window once and leaves it once, so the two pointers together take 2n steps. The work is O(n) even though the inner loop is nested inside the outer one, which is the part worth saying out loud in an interview.

Drop the positivity and this breaks: a negative value can make a longer window sum less than a shorter one, so a passed index may still matter. That version needs a monotonic deque over prefix sums, and it is a genuinely harder problem.

Complexity. Time O(n) · Space O(1)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def shortest_subarray(nums, target):
    n = len(nums)
    best, lo, total = n + 1, 0, 0
    for hi, value in enumerate(nums):
        total += value
        while total >= target:            # shrink while it still qualifies
            best = min(best, hi - lo + 1)
            total -= nums[lo]
            lo += 1
    return 0 if best == n + 1 else best

#include <vector>
#include <algorithm>

int solve(const std::vector<int>& nums, long long target) {
    const int n = static_cast<int>(nums.size());
    int best = n + 1, lo = 0;
    long long total = 0;                       // 64-bit: the sum can reach 10^9
    for (int hi = 0; hi < n; ++hi) {
        total += nums[hi];
        while (total >= target) {              // shrink while it still qualifies
            best = std::min(best, hi - lo + 1);
            total -= nums[lo];
            ++lo;
        }
    }
    return best == n + 1 ? 0 : best;
}

class Solution {
    public int shortestSubarray(int[] nums, long target) {
        int n = nums.length, best = n + 1, lo = 0;
        long total = 0;                            // 64-bit: the sum can reach 10^9
        for (int hi = 0; hi < n; hi++) {
            total += nums[hi];
            while (total >= target) {              // shrink while it still qualifies
                best = Math.min(best, hi - lo + 1);
                total -= nums[lo];
                lo++;
            }
        }
        return best == n + 1 ? 0 : best;
    }
}

function shortestSubarray(nums, target) {
  const n = nums.length;
  let best = n + 1, lo = 0, total = 0;
  for (let hi = 0; hi < n; hi++) {
    total += nums[hi];
    while (total >= target) {             // shrink while it still qualifies
      best = Math.min(best, hi - lo + 1);
      total -= nums[lo];
      lo++;
    }
  }
  return best === n + 1 ? 0 : best;
}

fn solve(nums: &[i64], target: i64) -> usize {
    let n = nums.len();
    let (mut best, mut lo, mut total) = (n + 1, 0usize, 0i64);
    for hi in 0..n {
        total += nums[hi];
        while total >= target {                // shrink while it still qualifies
            best = best.min(hi - lo + 1);
            total -= nums[lo];
            lo += 1;
        }
    }
    if best == n + 1 { 0 } else { best }
}

import Data.Array

-- An array rather than a list, so that dropping from the left stays O(1) and the
-- whole scan stays linear. go carries: right end, left end, running sum, best so far.
solve :: [Int] -> Int -> Int
solve nums target
  | best > n  = 0
  | otherwise = best
  where
    n    = length nums
    arr  = listArray (0, n - 1) nums
    best = go 0 0 0 (n + 1)
    go hi lo total acc
      | hi >= n   = acc
      | otherwise = let (lo', total', acc') = shrink lo (total + arr ! hi) acc
                    in go (hi + 1) lo' total' acc'
      where
        shrink l t a                                 -- shrink while it still qualifies
          | t >= target = shrink (l + 1) (t - arr ! l) (min a (hi - l + 1))
          | otherwise   = (l, t, a)

Variants to try

What if the values can be negative? (Prefix sums plus a monotonic deque, still O(n), but the argument is much harder.)
Return the subarray itself rather than its length: keep the lo index alongside the best length.
Shortest subarray with sum exactly the target: the monotone argument fails, and a hash map of prefix sums replaces it.
Longest subarray with sum at most the target: the same window, with the comparison reversed.

Next problems

Medium20 min

Shortest subarray with a sum at least the target

Examples

Constraints

Hints

Where people lose marks

Dry run on `[2,3,1,2,4,3],7`

How to think about it

The solution, in six languages

Variants to try

Next problems

Shortest window holding every kind

Shortest window containing every letter

Best total over k consecutive days

Keep going

Shortest window holding every kind

Shortest window containing every letter

Best total over k consecutive days

The pattern behind it

Shortest subarray with a sum at least the target

Examples

Constraints

Hints

Where people lose marks

Dry run on [2,3,1,2,4,3],7

How to think about it

The solution, in six languages

Variants to try

Next problems

Shortest window holding every kind

Shortest window containing every letter

Best total over k consecutive days

Keep going

Shortest window holding every kind

Shortest window containing every letter

Best total over k consecutive days

The pattern behind it

Dry run on `[2,3,1,2,4,3],7`