Shortest soak

Water counts only if it lands without a gap. The run must reach the target and waste nothing, and the obvious loop gets the second half wrong.

The problem

A drip controller waters a bed in pulses and logs the litres each pulse delivered, in order. Soil holds water only when it arrives in one continuous soak, so the pulses counted toward a soak must be consecutive in the log — you cannot skip a weak pulse in the middle and keep the run.

A bed needs at least litres in one soak, and a long soak wastes runtime the controller owes other beds. Find the fewest consecutive pulses whose total reaches the target, or 0 if the whole log falls short.

Input. pulses — a list of positive integers, litres per pulse in order. litres — an integer, the volume the bed needs.

Output. The length of the shortest consecutive run totalling at least litres, or 0 if none does.

Example.

pulses = [4, 2, 1, 7, 3, 2, 5], litres = 10   ->  2

The run [7, 3] delivers exactly 10. No single pulse reaches it, and every other adjacent pair falls short.

A second example, where the run has to be trimmed after it qualifies:

pulses = [1, 1, 1, 8, 1, 1], litres = 8   ->  1
pulses = [4, 2, 1],          litres = 12  ->  0

Extending from the first pulse reaches 8 only at the fourth, yet the pulse of 8 does it alone. The second log totals 7.

Constraints.

• 1 <= len(pulses) <= 10^5
• 1 <= pulses[i] <= 10^4
• 1 <= litres <= 10^9
• Every pulse delivers a strictly positive volume.

Hints

Approach

Brute force

Try every starting pulse and extend until the total reaches the target: up to n(n + 1) / 2 additions, around 5 billion for 10⁵ pulses, most of them re-adding sums an earlier start already computed.

The insight

Every pulse is positive, so a run's total only rises when you extend it right and only falls when you trim it from the left — which means the left edge never has to move backwards.

For each right edge you want the latest start that still reaches the target. Because totals are monotone in the window, that latest start is non-decreasing as the right edge advances, so one forward sweep of each pointer covers every candidate and each pulse is added once and removed at most once.

Positivity is the precondition doing the work: with a negative reading the total stops being monotone in the window and the left edge could need to retreat.

Algorithm

1. Set start = 0, total = 0, best larger than n.
2. For each end, add pulses[end] to total.
3. While total >= litres, record end - start + 1 if it beats best, subtract pulses[start], advance start.
4. Return best, or 0 if it was never set.

Complexity

Time O(n) — end advances n times and start at most n times, so at most 2n moves whatever the target. Space O(1): a running total and two indices.

Solution

"""Shortest soak — two pointers growing and trimming a window of pulses."""


def solve(pulses, litres):
    start = 0
    total = 0
    best = len(pulses) + 1          # sentinel: longer than any real run
    for end, volume in enumerate(pulses):
        total += volume
        # Invariant: total is the sum of pulses[start..end]. Because every pulse
        # is positive, trimming from the left can only lower it, so the latest
        # qualifying start for this end is found by trimming while it still fits.
        while total >= litres:
            if end - start + 1 < best:
                best = end - start + 1
            total -= pulses[start]
            start += 1
    return 0 if best == len(pulses) + 1 else best

TESTS = [
    (([4, 2, 1, 7, 3, 2, 5], 10), 2),
    (([1, 1, 1, 8, 1, 1], 8), 1),
    (([4, 2, 1], 12), 0),
    (([9], 9), 1),
    (([1, 1, 20], 5), 1),
    (([3, 3, 3, 3], 12), 4),
    (([10000], 10000), 1),
]

Pitfalls

• Recording the first run that reaches the target and moving on. On [1, 1, 1, 8, 1, 1] with a target of 8 that reports 4. The window must be trimmed from the left before it is measured.
• Using if instead of while for the trim. One large pulse carries the total far past the target, and a single trim leaves the window too long: on [1, 1, 20] with a target of 5 it reports 3 where the answer is 1.
• Returning the sentinel when nothing qualifies. A best left at infinity, or at n + 1, escapes into the schedule as a run length; report 0. The same slip hides on a log with corrective negative readings, where the monotone-total argument fails outright.

Variants

• No repeats on air — the same forward-only edges, trimmed to restore a rule rather than to reach a total, and answering with the longest window rather than the shortest.
• Cones on the loom — a window whose legality is a tunable budget on distinct values.