Module 01 · Execution Grammar and State Mutation

005. First Cumulative Threshold Crossing

Bridge · Download this solution · All solutions and shared helpers

Problem

Given integers nums and target, return the first zero-based index i for which sum(nums[:i+1]) >= target. Return -1 if no nonempty prefix qualifies. Values may be negative, so later prefixes can fall below the threshold again. Even when target <= 0, test actual nonempty prefixes rather than returning an imaginary index.

Examples

Example 1

first_threshold([2, 4, 3], 8)
=> 2

Nine reaches or exceeds eight.

Example 2

first_threshold([], 0)
=> -1

The contract excludes the empty prefix.

Example 3

first_threshold([5, -10, 8], 4)
=> 0

A later decline cannot erase the first crossing.

Reveal the worked solution and reasoning

Why this mechanism works

Only the earliest qualifying prefix matters. Update the cumulative sum before testing, because the question includes the current element. A left-to-right scan establishes earliestness automatically. Negative numbers prevent treating this predicate as globally monotone, but do not invalidate the scan.

State and boundaries

total includes the current value at the check. All earlier nonempty prefixes have failed if execution has not returned.

Protocol

Start total at zero.
Add nums[i].
Test total >= target.
Return i immediately on success.
Return -1 after all candidates fail.

Visualization

prefix sums: 2 -> 6 -> 9
target:                  8
first qualifying index:  2

Python implementation

def first_threshold(nums, target):
    total = 0
    for i, value in enumerate(nums):
        total += value
        if total >= target:
            return i
    return -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

first_threshold([2, 4, 3], 8)

L2 first_threshold: total = 0
nums=[2, 4, 3]; target=8; total=0

L3 first_threshold: for i, value in enumerate(nums):
nums=[2, 4, 3]; target=8; total=0; i=0; value=2

L4 first_threshold: total += value
nums=[2, 4, 3]; target=8; total=2; i=0; value=2

L3 first_threshold: for i, value in enumerate(nums):
nums=[2, 4, 3]; target=8; total=2; i=1; value=4

L4 first_threshold: total += value
nums=[2, 4, 3]; target=8; total=6; i=1; value=4

L3 first_threshold: for i, value in enumerate(nums):
nums=[2, 4, 3]; target=8; total=6; i=2; value=3

L4 first_threshold: total += value
nums=[2, 4, 3]; target=8; total=9; i=2; value=3

Result: 2. Nine reaches or exceeds eight.

first_threshold([], 0)

L2 first_threshold: total = 0
nums=[]; target=0; total=0

Result: -1. The contract excludes the empty prefix.

Why the solution is correct

The accumulator is correct by prefix extension. Every smaller index has already been tested and rejected when an index is returned, so the answer is earliest. If the scan ends, every admissible prefix has failed.

Time and space

O(n) worst-case time and O(1) auxiliary space; early success may use fewer iterations.

Common mistakes

Testing before adding shifts the reported index. Checking equality instead of >= misses a prefix that jumps over the target.

Reasoning card

State: total includes the current value at the check. All earlier nonempty prefixes have failed if execution has not returned.

Invariant: Before each check, total includes the current value.

Decision to rehearse: Update before checking and return early.

Finish: Return -1 after all candidates fail

Transfer exercise

Return all crossing indices instead of the first. Does a crossing mean qualifying, or moving from below to above? Specify that distinction first.