# Where the Deltas Settle

> Every stretch of the stream tells its own story. Count the ones that settle to your number.

Canonical URL: <https://datadriven.io/problems/where_the_deltas_settle>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

A monitoring export hands you `nums`, a sequence of per-interval integer deltas that can be positive, negative, or zero. Count how many contiguous stretches of `nums` sum to exactly `k`.

## Worked solution and explanation

### What this really is

Strip the wording away and this is a prefix-sum counting problem wearing a 'find the stretches' costume. The skill being probed: can you turn 'the sum of nums[i..j] equals k' into 'two running totals differ by k', so a quadratic scan collapses into one pass? Anyone can write the nested loop. The trap is the seed: you must pretend an empty prefix of total 0 has already been seen once, or every stretch that starts at index 0 and lands on k silently goes uncounted, and you are off by exactly one per such stretch.

---

### Break down the requirements

#### Step 1: Recognize the running-total identity

The sum of nums[i..j] equals prefix[j+1] minus prefix[i]. So 'how many stretches sum to k' becomes 'for each position j, how many earlier running totals equal prefix[j+1] minus k'. That converts a quadratic problem into a single scan with a constant-time lookup.

#### Step 2: Seed the map with running total 0

Initialize counts[0] = 1 so a stretch that begins at index 0 and whose running total already equals k gets credited. Forgetting this seed is the single most common bug; it undercounts by one for every such stretch, which is exactly why the [0, 0, 0] with k = 0 case is so revealing.

#### Step 3: One pass, look up before you write

Walk the array once, maintaining running_sum. At each element, add counts.get(running_sum - k, 0) to the answer first, then bump counts[running_sum]. Order matters: look up before you write, so the current position never counts itself as a zero-length stretch.

---

### The solution

**Running-total hash map in one pass**

```python
def subarray_sum(nums: list, k: int) -> int:
    counts = {0: 1}
    running_sum = 0
    answer = 0
    for x in nums:
        running_sum += x
        answer += counts.get(running_sum - k, 0)
        counts[running_sum] = counts.get(running_sum, 0) + 1
    return answer
```

> **Cost Analysis**
>
> Time is O(n): one pass over nums with average O(1) dictionary work per step. Space is O(n) worst case when every running total is unique. The brute-force O(n^2) version would time out on inputs of 100k or more, which is why this prompt shows up on senior loops.

> **Interviewers Watch For**
>
> Whether you derive the running-total identity out loud, whether you reach for the counts[0] = 1 seed without prompting, and whether you handle negatives, which break window-shrinking approaches that assume the sum only grows as you extend. Strong candidates also note this generalizes to stretches whose sum is divisible by k with a modulo twist.

> **Common Pitfall**
>
> Reaching for a sliding window. It works only when every value is non-negative; with negatives, extending the window can both raise and lower the sum, so shrinking from the left no longer tracks a monotone change. The running-total map handles negatives for free because it counts every prefix, not just the windows a pointer can reach.

---

## Common follow-up questions

- How would you return the actual stretches instead of just the count? _(store lists of indices in the map; trade O(1) lookup space for O(n) per match.)_
- What changes if you need stretches whose sum is divisible by k? _(key the map by running_sum % k instead of running_sum; mention negative-modulo handling.)_
- How would you parallelize this over a huge stream? _(discuss splitting the stream into chunks, computing local running-total maps per chunk, then a merge step that adjusts for the offset between chunks.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/where_the_deltas_settle)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.