EF-T03: Count Signed Target-Sum Ranges

Exercise contract#

Given an array of signed integers and a signed target, return the number of nonempty contiguous ranges whose total equals the target. Empty input returns 0. Values, prefix totals, target, and the result must use a numeric model wide enough for the declared bounds; the Java solution uses long.

Constraints

• 0 <= number of values <= 200,000.
• -1,000,000,000 <= each value <= 1,000,000,000.
• -100,000,000,000,000 <= target <= 100,000,000,000,000.
• Return a 64-bit count; the maximum possible count n(n+1)/2 fits for the declared n.
• Ranges are nonempty and contiguous; input values may be zero or negative.

Examples

values=[2,-1,-1,2,-2], target=0

4The valid ranges are indices [0,3), [0,5), [1,4), and [3,5).

values=[0,0,0], target=0

6Every one of the three length-one, two length-two, and one length-three ranges has total zero.

Derive the approach#

Baseline: Enumerate every left boundary, extend the right boundary while accumulating a running total, and increment the answer on a match. This is correct for signed values but takes O(n^2) time.

1. Let prefix[r] be the total before index r, with prefix[0] = 0.
2. A range [left, right) totals target exactly when prefix[right] - prefix[left] = target.
3. At a current boundary with total current, every earlier prefix equal to current - target starts one valid range.
4. Store how many times each earlier prefix total has occurred, not just whether it occurred.
5. Count matches before recording the current prefix so a boundary cannot pair with itself and create an empty range.
6. Initialize total zero with count one so ranges beginning at index zero are included.

Time

O(n) expected time for n values.

Space

O(u) auxiliary space for u distinct prefix totals, at most O(n).

Assumptions

Map operations are expected O(1); Python integers are arbitrary precision, while the declared bounds keep Java prefix totals and counts within signed 64-bit range.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def count_target_ranges(values, target):
    prefix_counts = {0: 1}
    current = 0
    answer = 0

    for value in values:
        current += value
        answer += prefix_counts.get(current - target, 0)
        prefix_counts[current] = prefix_counts.get(current, 0) + 1

    return answer

static long countTargetRanges(long[] values, long target) {
    Map<Long, Long> prefixCounts = new HashMap<>();
    prefixCounts.put(0L, 1L);
    long current = 0L;
    long answer = 0L;

    for (long value : values) {
        current = Math.addExact(current, value);
        answer = Math.addExact(answer, prefixCounts.getOrDefault(current - target, 0L));
        prefixCounts.merge(current, 1L, Long::sum);
    }
    return answer;
}

Deterministic test plan#

Transfer and follow-ups#

• Return one earliest matching range by storing an appropriate earlier prefix index instead of only counts.
• For a stream, maintain the same prefix state incrementally and explain when old prefixes may or may not be discarded.

Explain the empty-prefix seed and check-before-update order, then give a signed counterexample to a sliding-window approach.

Authorship and review#

Original Engineering Foundry prompt, examples, explanations, and verification programs using standard algorithmic techniques. This is not attributed to an employer and is not evidence of interview frequency.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09