How do you solve Minimum Size Subarray Sum?

Use two pointers, left and right, to define a sliding window. Expand right pointer, adding nums[right] to the window sum. When the sum is at least target, update the minimal length and contract the window from the left by subtracting nums[left] and moving left forward. Repeat until right reaches the end. Return 0 if no valid subarray is found.

What pattern does Minimum Size Subarray Sum use?

The Pattern: Sliding Window (Variable Size Window) The Heuristic: When dealing with contiguous subarrays and a sum or condition that can be incrementally updated, use two pointers to expand and contract the window dynamically, exploiting monotonic properties to achieve O(n) time.

Minimum Size Subarray Sum — Sliding Window

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

O(n). Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.

Problem

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray of which the sum is at least target. If there is no such subarray, return 0.

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Example

Input: target = 7, nums = [2,3,1,2,4,3]

Output: 2

The brute-force approach would check every possible subarray, summing elements and comparing to target, which is O(n²) and inefficient. The optimal approach uses a sliding window to maintain a running sum of a contiguous subarray. Starting with both pointers at the beginning, the window expands by moving the right pointer and adding elements until the sum reaches or exceeds the target. Then, the window contracts from the left to find the smallest valid subarray. For the example, the window first expands to include [2,3,1,2] with sum 8, then contracts from the left to [4,3] with sum 7, which has length 2, the minimal length.

Approach

Straightforward Solution

A brute-force solution checks all subarrays, summing each, resulting in O(n²) time complexity, which is too slow for large inputs.

Core Observation

The problem requires finding the shortest contiguous subarray with sum at least target. Because all numbers are positive, the sum of the window strictly increases when expanding right and strictly decreases when contracting left, enabling a two-pointer sliding window approach.

Path to Optimal

Preview

The key insight is that with positive integers, the sum of a window increases as the right pointer moves forward and decreases as the left pointer moves forward…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers, left and right, to define a sliding window. Expand right pointer, adding nums[right] to the window sum…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.

Space

O(1)

Only a few variables are used to track pointers and sums, with no additional data structures proportional to input size.

Solution

Python

1class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
      res = float("inf")
      left = 0
      window_sum = 0
6
      for right, value in enumerate(nums):
          window_sum += value
          while window_sum >= target:
              res = min(res, right - left + 1)
              window_sum -= nums[left]
              left += 1
13
      return 0 if res == float("inf") else res

Step-by-Step Solution

1

Initialize Sliding Window State and Result

3res = float("inf")
4left = 0
5window_sum = 0

Objective

To set up variables for tracking the minimal subarray length, the left pointer, and the current window sum.

Key Insight

Initializing the result to infinity allows easy comparison to find the minimal length. The left pointer starts at zero to represent the window's start, and the window sum starts at zero to accumulate values as the window expands. This setup is essential for the sliding window to function correctly.

Interview Quick-Check

Core Logic

Initializing result to infinity ensures any valid subarray length found will replace it, enabling minimal length tracking.

State & Boundaries

Starting left pointer at zero and window sum at zero correctly represents an empty window before iteration.

2

Expand Window and Contract to Find Minimal Length

To iterate through the array with the right pointer, expanding the window sum, and contract from the left when the sum meets or exceeds the target to minimize the window size.

3

Return Result or Zero if No Valid Subarray Found

To return the minimal length found or zero if no subarray meets the target sum.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 9 Critical

while window_sum >= target:

While the window sum is at least the target, attempt to contract the window.

This while loop is the core of the sliding window technique; it contracts the window only when the sum condition is met, ensuring minimal length subarrays are found without missing any valid candidates.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does the sliding window approach work efficiently only because the array contains positive integers?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Size Subarray Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Size Subarray Sum drill

or drill a free problem

1	`class Solution:`
2	`def minSubArrayLen(self, target: int, nums: List[int]) -> int:`
3	`res = float("inf")`
4	`left = 0`
5	`window_sum = 0`
6
7	`for right, value in enumerate(nums):`
8	`window_sum += value`
9	`while window_sum >= target:`
10	`res = min(res, right - left + 1)`
11	`window_sum -= nums[left]`
12	`left += 1`
13
14	`return 0 if res == float("inf") else res`