Minimum Size Subarray Sum – Solution & Complexity

Q: What is the time and space complexity of Minimum Size Subarray Sum?

The optimal Minimum Size Subarray Sum solution runs in `O(n)` time and `O(1)` space. A variable-size sliding window expands right and shrinks left once the sum reaches target.

Q: What is the most efficient way to solve Minimum Size Subarray Sum?

A variable-size sliding window expands right and shrinks left once the sum reaches target. This gives `O(n)` time complexity, and is a classic arrays, sliding window, and two pointers problem.

Q: How do you solve Minimum Size Subarray Sum in Python, JavaScript, Java, Go & Rust?

We provide a worked Minimum Size Subarray Sum solution in Python, JavaScript, Java, Go & Rust with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Minimum Size Subarray Sum an easy or hard interview question?

Minimum Size Subarray Sum is generally rated **Medium**. It tests arrays, sliding window, and two pointers, which are common coding-interview patterns.

Solution Walkthrough

1. Understand the Goal

Find the length of the shortest contiguous run of nums whose sum is >= target, or 0 if no run reaches it.
All values are positive — that constraint is what makes a sliding window valid here instead of needing prefix sums with binary search.

2. Choose the Core Pattern

Variable-size sliding window with two pointers: because every element is positive, the running window sum is monotonic in both directions — growing the window (moving right) can only increase the sum, and shrinking it (moving left) can only decrease it.
That monotonicity is exactly what breaks with negative values: shrinking the window could increase the sum instead (removing a negative number raises the total), so the greedy "shrink while sum is big enough" rule would no longer be safe, and you'd need a different technique (e.g. prefix sums with a monotonic deque, since binary search alone doesn't work either once prefix sums stop being non-decreasing).

3. Build the Algorithm

Expand the window by moving right across every index once, adding nums[right] to a running windowSum.
After each addition, while windowSum >= target, the current window is a valid candidate: record its length if it's the best seen so far, then shrink from the left by subtracting nums[left] and advancing left — shrinking is always safe to attempt again immediately, since the sum only goes down and might still satisfy >= target.
Because left only ever advances and never resets backward, each index is added to the sum once and removed at most once, giving O(n) total work despite the nested loop.

4. Check Edge Cases

No subarray reaches target (e.g. all values are 1 and target exceeds the total sum): the inner while loop never triggers, and the best-length sentinel must be recognized and converted to 0 in the return value.
The entire array is required (e.g. target equals the whole array's sum, achieved only once at the end): the window must be allowed to grow all the way to right == len(nums) - 1 before it first becomes valid.
A single element already meets target: the window shrinks immediately back down to length 1 on the same iteration it became valid.

5. Final Solution and Complexity

Time complexity is O(n).
Space complexity is O(1).

def min_sub_array_len(target: int, nums: list[int]) -> int:
    left = 0
    window_sum = 0
    best = len(nums) + 1
    for right, value in enumerate(nums):
        window_sum += value
        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return 0 if best == len(nums) + 1 else best

Minimum Size Subarray Sum – Solution & Complexity

Solution Walkthrough

1. Understand the Goal

2. Choose the Core Pattern

3. Build the Algorithm

4. Check Edge Cases

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Minimum Size Subarray Sum?

What is the most efficient way to solve Minimum Size Subarray Sum?

How do you solve Minimum Size Subarray Sum in Python, JavaScript, Java, Go & Rust?

Is Minimum Size Subarray Sum an easy or hard interview question?

See also