46. Count Handle-Time Subarrays

Problem

Fin's ops team logs the handle-time (in minutes, and occasionally negative when a correction or credit is applied) for a sequence of conversations handled back to back. Before scheduling a review block, they want to know how many contiguous windows of conversations have a total handle-time exactly equal to a target budget, since any such window is a natural, self-contained chunk to pull for review without cutting into a conversation's own time.

Given a list of handle-times and a target sum, count the number of contiguous subarrays whose elements sum exactly to the target. Handle-times can be negative, so a naive "shrink the window when the sum gets too big" two-pointer approach doesn't work directly.

Source: src/46_count_handle_time_subarrays.py

def count_subarrays_with_sum(handle_times: list[int], target: int) -> int:

>>> count_subarrays_with_sum(handle_times=[1, 1, 1], target=2)
2

>>> count_subarrays_with_sum(handle_times=[1, -1, 0], target=0)
3

Step-by-Step Approach

1. Maintain a running prefix_sum as you scan the array left to right.
2. A subarray (i, j] sums to target exactly when prefix_sum[j] - prefix_sum[i] == target, i.e. when some earlier prefix sum equals prefix_sum[j] - target.
3. Keep a hashmap of how many times each prefix-sum value has been seen so far, seeded with {0: 1} to account for subarrays that start at index 0.
4. At each step, add prefix_counts[prefix_sum - target] to the running result — that's the number of earlier prefixes that would close out a window summing to target ending here.
5. Then increment prefix_counts[prefix_sum] so later elements can match against this prefix.
6. Return the accumulated count after scanning the whole array.

The key insight is turning "does some contiguous window sum to target" into "have we seen this specific prefix-sum value before," which collapses an O(n²) brute-force scan of every window into a single O(n) pass with a hashmap.

Reference solution

from collections import defaultdict


def count_subarrays_with_sum(handle_times: list[int], target: int) -> int:
    # prefix-sum + hashmap of prefix-sum frequencies, O(n) time / O(n) space
    # missing key defaults to 0
    prefix_counts: dict[int, int] = defaultdict(int)
    # seed empty prefix so windows starting at index 0 count
    prefix_counts[0] = 1
    prefix_sum = 0
    result = 0
    for handle_time in handle_times:
        prefix_sum += handle_time
        # count earlier prefixes matching target
        result += prefix_counts[prefix_sum - target]
        # record after counting, so len-0 windows can't self-match
        prefix_counts[prefix_sum] += 1
    return result

Key Functions & Tricks

• from collections import defaultdict — dict subclass that auto-creates missing keys instead of raising KeyError.
• defaultdict(int) — int() default-factory returns 0 for an unseen prefix sum.
• prefix_sum[j] - prefix_sum[i] == target — prefix-sum trick, turns O(n²) window scan into O(n) hashmap lookups.
• prefix_counts[0] = 1 — seeds the "empty prefix" so subarrays starting at index 0 can match.
• Exact-value hashmap lookup, not a sliding window — handles negative/zero handle-times with no monotonicity requirement.
• Lookup before increment inside the loop — prevents a zero-length window from counting itself when target == 0.

How to Recognize This Pattern