Generated by Codex with GPT-5

Quick facts

Problem gist

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

The important detail is that every number is positive. That one constraint makes the optimal solution much simpler: expanding a window to the right can only increase its sum, and shrinking it from the left can only decrease its sum.

Deriving the optimal solution

A brute-force approach tries every starting index, then extends the subarray until the sum reaches target. That works, but it can revisit the same elements many times, so it costs O(n^2) in the worst case.

The better idea is to keep one moving window [left, right]:

  1. Move right forward and add nums[right] to the current sum.
  2. Once the current sum is at least target, the current window is valid.
  3. Record its length, then move left forward while the window still stays valid.

This works because all numbers are positive. When the window is valid, removing from the left is the only way to make it shorter for the current right. If removing too much makes the sum fall below target, no smaller window ending at this same right can work, so the algorithm safely moves on.

Each index enters the window once and leaves the window once. That gives the optimal O(n) time solution.

Python solution

from typing import List


class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        """
        Return the minimum length of a contiguous subarray whose sum is at
        least target. The input numbers are positive, which makes the sliding
        window invariant valid.
        """
        shortest_length = len(nums) + 1
        current_sum = 0
        left = 0

        for right, value in enumerate(nums):
            current_sum += value

            # While the window is valid, shrink it to find the shortest
            # valid window ending at this right boundary.
            while current_sum >= target:
                window_length = right - left + 1
                shortest_length = min(shortest_length, window_length)

                current_sum -= nums[left]
                left += 1

        if shortest_length == len(nums) + 1:
            return 0
        return shortest_length

Complexity

Time complexity is O(n) because the right pointer advances once through the array and the left pointer also advances at most once through the array.

Space complexity is O(1) because the algorithm stores only a few counters and pointers.

Interview follow-ups

How would you return the actual subarray instead of only its length?

Store the best pair of boundaries whenever a shorter valid window is found. The sliding window logic stays the same: expand on the right, shrink from the left while the sum is large enough, and update (best_left, best_right) before removing nums[left].

This still works because the positive-number invariant has not changed. The time complexity remains O(n), and the extra space is O(1) if returning indices. Returning a copied list slice costs O(k) additional space, where k is the answer length.

What changes if the array can contain negative numbers?

The sliding window no longer works. With negative numbers, adding a value on the right might decrease the sum, and removing a value from the left might increase it. That breaks the monotonic behavior the two-pointer solution depends on.

For mixed positive and negative values, use prefix sums with a monotonic deque. For each index, the goal is to find the earliest prefix sum that is at most current_prefix - target. The deque keeps candidate prefix indices in increasing prefix-sum order, which lets the algorithm discard candidates that can never produce a better answer. This is the core idea behind the harder variant, shortest subarray with sum at least K.

The complexity is still O(n) time because each prefix index is pushed and popped at most once. The tradeoff is O(n) space for the prefix candidates.

Yes. Since all values are positive, prefix sums are strictly increasing. For each left boundary, binary search can find the first right boundary where the prefix-sum difference reaches target.

That solution is usually easier to justify if someone is already thinking in prefix sums, but it costs O(n log n) time instead of O(n). It uses O(n) space for the prefix array. In an interview, it is a good stepping stone, but the sliding window is the preferred final answer for this exact problem.

How would you answer many target queries against the same array?

If there are many different target values, the best approach depends on the constraints. Running the O(n) sliding window once per query is often good enough when the number of queries is small or moderate.

For very large query counts, there is no simple one-size-fits-all improvement for arbitrary positive arrays because each target can change which window length is optimal. A practical answer is to discuss constraints first. If n is small, precomputing all subarray sums by length may be acceptable despite higher preprocessing cost. If the values or query range are bounded, specialized counting or prefix-sum indexing may help. The key interview signal is recognizing that the single-query sliding window is optimal, while multi-query optimization needs more structure from the input.