DSA Minimum Size Subarray with Sum at Least Target

The problem

Minimum Size Subarray Sum asks for one length. Find the shortest run of neighbouring values whose sum reaches at least a target, and return its length.

A run may be the whole list, or a single value, or anything between. If no run reaches the target, the answer is 0. Zero is a signal here, not a length that was found.

Every value in the list is positive. That fact is part of the problem, and the fast method depends on it. The input is the list and the target, and the output is one integer.

cases = [
    ([2, 3, 1, 2, 4, 3], 7, 2),
    ([1, 4, 4], 4, 1),
    ([1, 2, 3, 4], 11, 0),
    ([1, 1, 1, 1], 4, 4),
    ([5], 5, 1),
]
for values, target, expected in cases:
    print("values", values, "target", target, "shortest:", expected)

Read one row at a time. In the first list, the run [4, 3] at the end reaches 7 in two values, and no single value reaches 7. In the third list, every value together sums to 10, so the target of 11 is out of reach and the answer is 0.

The fourth row needs all four values. Each shrink attempt there breaks the sum, which is why the answer equals the length of the list.

Intuition: growing the window only finds the first window

A first idea grows a window from the left edge. It adds values until the sum reaches the target. It then stops and reports that window.

Stopping is the mistake. The first valid window is rarely the shortest one. Later values may be larger, so a later window can reach the target with fewer of them.

values = [2, 3, 1, 2, 4, 3]
target = 7
total = 0
for right in range(len(values)):
    total += values[right]
    if total >= target:
        print("first valid window:", values[:right + 1], "sum:", total, "length:", right + 1)
        break
print("correct answer: 2, from the run [4, 3]")

The grow-only method reports 4, and the correct answer is 2. It never looked past the first success. It also never tried removing values from the left of its window, where its own sum of 8 had room to spare.

The repair keeps growing, but it also shrinks. Every time the sum reaches the target, the window is a candidate. The left edge then removes values while the sum still holds, hunting for a shorter candidate ending at the same place.

Brute force: sum every run

The straightforward method lists every run of values. For each start, it walks to every end and keeps a running sum. Each time the sum reaches the target, it records the length if it beats the best so far.

The code counts its additions. One addition happens for each value folded into a run sum. That printed count is the cost of checking everything.

def brute_shortest(values, target):
    best = 0
    adds = 0
    for start in range(len(values)):
        total = 0
        for end in range(start, len(values)):
            total += values[end]
            adds += 1
            if total >= target and (best == 0 or end - start + 1 < best):
                best = end - start + 1
    return best, adds

for values, target in [([2, 3, 1, 2, 4, 3], 7), ([1, 2, 3, 4], 11)]:
    best, adds = brute_shortest(values, target)
    print("values", values, "target", target, "shortest:", best, "adds:", adds)

The answers are right, including the unreachable case. The waste is the re-adding. The opening values of the list are folded into one run sum after another, once for every start that includes them.

Positivity is what lets a faster method avoid that waste. Adding a value never lowers a sum, and removing a value from the left never raises one. A window can therefore slide in one direction without ever needing to step back.

The optimal solution: grow, record, then shrink

The window is the current run of values, with its sum kept alongside it. The right edge grows the window. The left edge shrinks it.

The key idea is one sentence. Because every value is positive, once the window sum reaches the target the only way to find a shorter valid window ending at the same right edge is to remove values from the left, so the code records each length and shrinks while the sum still holds.

def shortest_window(values, target):
    left = 0
    total = 0
    best = 0
    for right in range(len(values)):
        total += values[right]
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= values[left]
            left += 1
    return best

cases = [
    ([2, 3, 1, 2, 4, 3], 7),
    ([1, 4, 4], 4),
    ([1, 2, 3, 4], 11),
    ([1, 1, 1, 1], 4),
    ([5], 5),
]
for values, target in cases:
    print("values", values, "target", target, "shortest:", shortest_window(values, target))

All five cases from the start of the article pass. The unreachable case returns 0 because the shrink loop never runs, so the best length is never set.

The record step sits inside the shrink loop, before each removal. That order matters. The window is recorded while it is still valid, and each removal then tests a shorter window that may also be valid.

Walkthrough: target 7 on [2, 3, 1, 2, 4, 3]

Follow the main case. The first valid window appears at right index 3, with sum 8 and length 4. Shrinking removes the opening 2, and the sum falls to 6, below the target, so the window grows again.

values = [2, 3, 1, 2, 4, 3]
target = 7
left = 0
total = 0
best = 0
for right in range(len(values)):
    total += values[right]
    while total >= target:
        if best == 0 or right - left + 1 < best:
            best = right - left + 1
        print("valid window:", values[left:right + 1], "sum:", total, "length:", right - left + 1, "best:", best)
        total -= values[left]
        left += 1
print("answer:", best)

The lengths arrive in the order 4, 4, 3, 3, 2. The last one is the run [4, 3], which reaches the target exactly. No single value in the list reaches 7, so no window found later could beat length 2.

Notice what the left edge did across the whole run. It moved forward only, and it never had to return to a value it had removed. Positivity guarantees that a removed value can never belong to a shorter valid window later.

Complexity

Time is O(n). The right edge visits each value once and the left edge moves forward at most n times in total, so the edge moves stay within twice n.

Space is O(1). The method keeps two edges, one running sum, and one best length, whatever the size of the list.

def edge_moves(values, target):
    left = 0
    total = 0
    moves = 0
    for right in range(len(values)):
        moves += 1
        total += values[right]
        while total >= target:
            total -= values[left]
            left += 1
            moves += 1
    return moves

def brute_adds(n):
    adds = 0
    for start in range(n):
        for end in range(start, n):
            adds += 1
    return adds

for n in [10, 20, 40]:
    print("n", n, "window edge moves:", edge_moves([2] * n, 7), "brute adds:", brute_adds(n))

The printed counts match the two claims. The window moves grow in step with n. The brute adds follow n times n plus one, over two, and pull away.

Edge cases and pitfalls

An empty list answers 0, because no run exists at all. A target that the whole list cannot reach also answers 0. The two cases share the signal, and both mean no valid window was found.

A single value can be the whole answer. It answers 1 when it reaches the target on its own, as the last case in section 1 shows.

def shortest_window(values, target):
    left = 0
    total = 0
    best = 0
    for right in range(len(values)):
        total += values[right]
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= values[left]
            left += 1
    return best

print("empty list:", shortest_window([], 7))
print("target unreachable:", shortest_window([1, 2, 3], 99))
print("one value reaches:", shortest_window([9], 7))
print("one value falls short:", shortest_window([3], 7))
print("whole list needed:", shortest_window([2, 2, 2], 6))

The largest pitfall is using this method on values that are not all positive. A negative value can lower a window sum, so a shrunk window might have become valid again later. That problem needs the prefix-sum method instead, which makes no positivity assumption.

A second pitfall is treating 0 as a found length. Zero is the starting value of the best variable and the unreachable signal. Code that reports a window must set the best length only inside the shrink loop, where a valid window actually exists.