Count Subarrays with a Target Sum
Combine prefix sums with a hash map.
Count Subarrays with a Target Sum is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
A Harder Question
Now the twist: count how many subarrays add up to a target k. Checking every pair is slow, but prefix sums plus a hash map crack it. 🎯
Reframe with Prefixes
A subarray sum equals prefix[r + 1] minus prefix[l]. So a sum of k means two prefix values differ by exactly k.
The Key Rearrangement
If the current prefix is P, you need an earlier prefix equal to P minus k. That rearrangement is the whole trick.
need = current_prefix - kCount, Do Not Search
Instead of scanning back each time, remember how often each prefix value has appeared. A running tally answers in O(1).
Use a Frequency Map
A dictionary maps each prefix value to how many times you have seen it. This map turns the lookup into instant counting.
from collections import defaultdict
seen = defaultdict(int)Seed the Empty Prefix
Before the loop, record that prefix 0 has appeared once. This seed lets subarrays starting at index 0 get counted.
seen[0] = 1The One-Pass Loop
For each element, update the running prefix, add the count of the needed value, then record the current prefix. One pass does it all.
total += x
count += seen[total - k]
seen[total] += 1Why Order Matters
You must add to the answer before recording the current prefix. Otherwise a zero-length range sneaks in and the count breaks.
The Speed Win
Each element does constant work, so the whole count runs in O(n). That beats the O(n squared) brute force on big inputs.
Negatives Welcome
Unlike sliding windows, this method handles negative numbers fine, because prefix differences stay valid no matter the signs.
A Classic Use Case
This pattern solves the famous subarray-sum-equals-k problem and many disguised variants on contest judges.
Quick Check
Your running prefix is P and the target is k.
Recap
You can count target-sum subarrays in O(n) using prefix sums and a frequency map. Seed prefix 0, then count before recording. ✅
Frequently asked questions
Is the “Count Subarrays with a Target Sum” lesson free?
Yes — the full text of “Count Subarrays with a Target Sum” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Count Subarrays with a Target Sum”?
Combine prefix sums with a hash map. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Count Subarrays with a Target Sum” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Build a Prefix Sum Array
- Sum Any Range with Subtraction
- Count Subarrays with a Target Sum
- Difference Arrays for Range Updates