Minimum Size Subarray Sum

MEDIUM✓ CHIP-TIMEDLC #209 — FULL STATEMENT ↗

The drill: Among all contiguous runs whose sum reaches a target, find the shortest — or report 0 if none does. Every value is positive, which is precisely what lets a window stretch and shrink without ever looking back.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A target sum and an array of positive values arrive together, and the task is to find the length of the shortest contiguous run of the array whose values add up to at least that target.

Every value in the array is strictly positive, so there's no trick of negative numbers canceling each other out — a run's sum only grows as it gets longer.

If no contiguous run ever reaches the target, even the entire array summed together, the answer is zero rather than some impossible length.

EX 01

target = 8 · nums = [3, 1, 4, 2, 5, 2]

→ 3

NO PAIR REACHES 8; A MID-ARRAY TRIO DOES

EX 02

target = 4 · nums = [1, 4, 4]

→ 1

A SINGLE ELEMENT ALREADY QUALIFIES

EX 03

target = 11 · nums = [1, 2, 3, 4]

→ 0

WHOLE ARRAY FALLS SHORT

array length runs from zero up to around one hundred thousand elements
every value in the array is strictly positive
the target sum is a positive integer
when no qualifying run exists, the answer is zero

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Positivity is the lever: growing a window can only raise its sum, shrinking can only lower it. What does that monotonicity make safe to skip?

HINT 2 THE STRUCTURE

Once a window's sum reaches the target, extending it is pointless — a longer qualifying window never beats a shorter one. Shrink instead.

HINT 3 ONE STEP FROM THE ANSWER

Two pointers: push right until the sum qualifies, then pull left while it still qualifies, recording the length at every qualifying moment. Each pointer crosses the array once.

COACH'S BOARD — THE PATTERN, STEP BY STEP

STRETCH THEN SHRINKPATTERN · SLIDING WINDOW — VARIABLE WIDTHtarget = 8 · nums = [3, 1, 4, 2, 5, 2]

RUNNING SUM · BEST LENGTH

— empty —

STEP 1

Target 8, all positive. Grow the window right while its sum falls short, then shrink it left while it still qualifies — track the shortest length.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/minimum-size-subarray-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        best = len(nums) + 1
        total = 0
        left = 0
        for right, v in enumerate(nums):
            total += v
            while total >= target:      # qualified: bank the length, then shrink
                best = min(best, right - left + 1)
                total -= nums[left]
                left += 1
        return 0 if best == len(nums) + 1 else best

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 12 LN

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        best = n + 1
        for start in range(n):
            total = 0
            for end in range(start, n):
                total += nums[end]
                if total >= target:               # first hit is the shortest from this start
                    best = min(best, end - start + 1)
                    break
        return 0 if best == n + 1 else best

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int best = nums.length + 1;
        int total = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            total += nums[right];
            while (total >= target) { // qualified: bank the length, then shrink
                best = Math.min(best, right - left + 1);
                total -= nums[left++];
            }
        }
        return best == nums.length + 1 ? 0 : best;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 14 LN

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int best = nums.length + 1;
        for (int start = 0; start < nums.length; start++) {
            int total = 0;
            for (int end = start; end < nums.length; end++) {
                total += nums[end];
                if (total >= target) { // first hit is the shortest from this start
                    best = Math.min(best, end - start + 1);
                    break;
                }
            }
        }
        return best == nums.length + 1 ? 0 : best;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED