Where the Deltas Settle

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
JPMorgan Chase

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.

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

Example 1

Input:

k = 2, nums = [1,1,1]

Output:

2

Example 2

Input:

k = 3, nums = [3,-1,1,2]

Output:

3

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
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

Common follow-up questions