# The Subarray Tally

> How many hidden windows hit the target?

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a list of integers and a target integer k, return the number of contiguous subarrays whose elements sum to exactly k.

## Worked solution and explanation

### Why this problem exists in real interviews

Subarray-sum-equals-k is one of the most-asked prefix-sum problems on real interview loops because the brute-force O(n^2) solution is obvious and tempting, but the optimal O(n) solution requires a specific insight: a prefix-sum hash map. Interviewers use it to separate candidates who memorized the trick from those who can derive it under pressure.

---

### Break down the requirements

#### Step 1: Recognize the prefix-sum identity

Sum of nums[i..j] equals prefix[j+1] - prefix[i]. So the question 'how many subarrays sum to k' becomes 'for each j, how many earlier prefixes equal prefix[j+1] - k'. That converts a quadratic problem into a single scan with a hash map lookup.

#### Step 2: Seed the map with prefix sum 0

Initialize counts[0] = 1 so that subarrays starting at index 0 with running_sum equal to k are counted. Forgetting this seed is the single most common bug; it silently undercounts by exactly one per such subarray.

#### Step 3: Single pass, increment after lookup

Walk the array once, maintaining running_sum. At each step, add counts.get(running_sum - k, 0) to the answer, then increment counts[running_sum] by 1. The order matters: lookup first, then write, so you never count the empty subarray ending at the current index.

---

### The solution

**Prefix-sum 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) with one pass over nums and O(1) average hash operations per step. Space is O(n) worst case for the prefix-sum map (when every prefix is unique). The brute-force O(n^2) solution would TLE on inputs of 100k or more, which is why interviewers favor this prompt for senior roles.

> **Interviewers Watch For**
>
> Whether you derive the prefix-sum identity out loud, whether you remember the counts[0] = 1 seed without prompting, and whether you handle negative numbers (which break sliding-window approaches that assume monotonicity). Strong candidates also call out that this generalizes to subarrays divisible by k with a modulo twist.

> **Common Pitfall**
>
> Using a sliding window. It works only when all numbers are non-negative; with negatives, expanding the window can both increase and decrease the sum, so shrinking from the left no longer corresponds to a monotone change. The prefix-sum map handles negatives naturally because it counts every prefix, not just contiguous windows.

---

## Common follow-up questions

- How would you return the actual subarrays 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 subarrays 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 segment trees or splitting the array, computing local prefix-sum 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/the_subarray_tally)
- [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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.