How do you count subarrays that sum to k? | Interview Question

Q: How do you count subarrays that sum to k?

**Target Audience:** Intermediate candidates — you should know arrays and hash maps; prefix sums are explained here and linked. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown in the **Verified** section was produced by actually running the Python code with `python3 main.py`; nothing is quoted from memory. ## 1. Why This Even Matters — A Story First Suppose you track your bank balance every day for a month, and you want to know how many stretches of consecutive days had a net change of exactly +700. Checking every possible stretch means comparing every start day with every end day — fine for a month, painful for ten years. Here is the shortcut. The net change over a stretch is simply "balance at the end minus balance just before the start". So a stretch ending today has a net change of +700 exact

The problem

Question presented to candidate: "Given a list of integers that may include negatives, and a target k, count how many contiguous subarrays sum to exactly k. Brute force is O(n squared) — can you do it in linear time in Python?"

What a strong answer should cover:

A subarray sum is P[j] - P[i], so count earlier prefixes equal to prefix - k.
A count map seeded with {0: 1}; count before recording; counts, not a set.
O(n) average time, O(n) space; brute force O(n²); why a sliding window fails with negatives.
Python specifics: collections.Counter returns 0 for a missing key without inserting it, unlike defaultdict; dict.get(key, 0) also works.
Edge cases: zeros, k = 0, subarrays starting at index 0.

Clarifying questions expected:

"Can the array contain negatives or zeros?" — decides between a sliding window and prefix sums.
"Do you want the count or the subarrays themselves, and how large can the sums get?"

Code / implementation expected: Yes — a one-pass Python function with a Counter or dict.

arrays
prefix-sum

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Intermediate candidates — you should know arrays and hash maps; prefix sums are explained here and linked. Difficulty: Medium Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown in the Verified section was produced by actually running the Python code with python3 main.py; nothing is quoted from memory.

1. Why This Even Matters — A Story First

Suppose you track your bank balance every day for a month, and you want to know how many stretches of consecutive days had a net change of exactly +700. Checking every possible stretch means comparing every start day with every end day — fine for a month, painful for ten years.

Here is the shortcut. The net change over a stretch is simply "balance at th

The solution is hidden so you can try first

11 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonPrefix sum + hash map on seven inputs

Practice

PythonBrute force vs hash map vs sliding window

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.