PPractick

The problem

A fraud-detection team looks at a customer's sequence of transactions (credits and debits, positive and negative) and flags every contiguous stretch whose net total is exactly K, a pattern associated with a known scam. They need the number of such stretches, not just the longest one. With negative values the sliding window doesn't apply, and checking every subarray is O(n²). Prefix sums with a hash map of counts give O(n): each earlier prefix equal to prefix − K marks one subarray ending here.

Example: [1, 1, 1], K = 2 → 2 (the subarrays at indices 0–1 and 1–2).

Function signature

int subarraySum(const vector<int>& nums, int k);  // number of contiguous subarrays with sum k

Test cases

Input (nums, k)	Output	Explanation
([1, 1, 1], 2)	2
([1, 2, 3], 3)	2	[1, 2] and [3]
([3, 4, 7, 2, -3, 1, 4, 2], 7)	4	[3, 4], [7], [7, 2, -3, 1], [1, 4, 2]
([1, -1, 0], 0)	3	[1, -1], [1, -1, 0], [0]
([0, 0, 0], 0)	6	Every subarray
([5], 3)	0

(Confirm: values can be negative or zero; count every (start, end) pair whose subarray sums to k.)

How interviewers phrase it

• "Count the number of subarrays whose sum equals K" (LeetCode 560).
• Relatives: longest subarray with sum K (S.No 75), subarrays with XOR K (S.No 95), subarrays divisible by K (LeetCode 974).

Clarifying questions to ask

1. Can values be negative? (Then the sliding window is out.)
2. Count or list the subarrays?
3. How large can the counts and sums get?

Follow-ups to expect

1. "Why seed the map with {0: 1}?"
2. "How does this differ from the longest-subarray version?"
3. "Why must you look up before inserting the current prefix?"
4. "Could the count overflow an int?"
5. "Complexity?"

Related questions

• Longest subarray with sum K Medium
• Largest Subarray with Sum 0 Medium
• Longest subarray with given sum K (positives) Medium
• Fruit Into Baskets Medium
• Maximum Points You Can Obtain from Cards Medium
• Subarrays with K Different Integers Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in