{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Minimum Size Subarray Sum – Solution & Complexity

Interview solutions
/
Minimum Size Subarray Sum

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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
Learn the Sliding Window pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Minimum Size Subarray Sum online (run code in the browser)3Sum solution (medium)3Sum Closest solution (medium)Container With Most Water solution (medium)Find the Duplicate Number solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?