Subarray Sum Equals K
Asked at Google, Meta, Microsoft, Apple, Salesforce
Problem
Given an array of integers and an integer k, count the total number of continuous subarrays whose sum equals k. This problem tests your understanding of prefix sums and hash map counting.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
Brute force: check every subarray (i to j). Calculate sum in O(n) per subarray. Total: O(n²). Too slow.
Key insight: prefix sum. If prefix_sum[j] - prefix_sum[i] == k, then the subarray from i+1 to j sums to k. Store prefix sums in a hash map for O(1) lookup.
The formula: for each position j, check if (prefix_sum[j] - k) exists in the map. If yes, there are that many subarrays ending at j that sum to k.
Critical edge case: initialize the map with {0: 1}. This handles subarrays that start from index 0. Without it, you miss subarrays where the prefix sum itself equals k.
Visual walkthrough for [1,2,3], k=3:
prefix_sum = 0, map = {0:1}
num=1: sum=1. Check 1-3=-2 in map? No. map={0:1, 1:1}. count=0.
num=2: sum=3. Check 3-3=0 in map? Yes, count+=1. map={0:1, 1:1, 3:1}. count=1.
num=3: sum=6. Check 6-3=3 in map? Yes, count+=1. map={0:1, 1:1, 3:1, 6:1}. count=2.
Result: 2 (subarrays [1,2] and [3])
Optimal Approach
Step 1: Initialize prefix_sum = 0, map = {0: 1}, count = 0.
Step 2: For each num in the array:
- Add num to prefix_sum
- Check if (prefix_sum - k) is in the map
- If yes, add map[prefix_sum - k] to count
- Increment map[prefix_sum]
Step 3: Return count.
Why it works: if prefix_sum[j] - prefix_sum[i] == k, the subarray from i+1 to j sums to k. The map stores how many times each prefix sum has occurred.
Time: O(n). Space: O(n).
What Trips People Up in Real Interviews
Confusing "subarray" with "subsequence." A subarray is contiguous. A subsequence can skip elements.
Not using prefix sums. The brute force is O(n²). Prefix sums with a hash map give O(n).
Forgetting that the prefix sum map needs a count of 0: 1. This handles the case where a subarray starting from index 0 sums to k.
Not handling negative numbers. The prefix sum approach works with negatives, but you can't use two pointers (the array isn't sorted).
Forgetting that prefix sums can repeat. If the same prefix sum occurs at multiple indices, the map must store COUNTS, not just the most recent index. Missing this undercounts subarrays.
Solution Code
from collections import Counter
def subarraySum(nums, k):
prefix = Counter()
prefix[0] = 1
total = count = 0
for num in nums:
total += num
count += prefix[total - k]
prefix[total] += 1
return countFrequently Asked Questions
What is the Subarray Sum Equals K problem?
Given an array of integers and an integer k, count the total number of continuous subarrays whose sum equals k. This problem tests your understanding of prefix sums and `hash map` counting.
How do you solve Subarray Sum Equals K?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Subarray Sum Equals K?
Subarray Sum Equals K is asked at Google, Meta, Microsoft, Apple, Salesforce. It is a medium difficulty problem.
What are common mistakes on Subarray Sum Equals K?
- Confusing "subarray" with "subsequence." A subarray is contiguous. A subsequence can skip elements.
- Not using prefix sums. The brute force is `O(n²)`. Prefix sums with a `hash map` give `O(n)`.
- Forgetting that the prefix sum map needs a count of 0: 1. This handles the case where a subarray starting from index 0 sums to k.
- Not handling negative numbers. The prefix sum approach works with negatives, but you can't use two pointers (the array isn't sorted).
- Forgetting that prefix sums can repeat. If the same prefix sum occurs at multiple indices, the map must store COUNTS, not just the most recent index. Missing this undercounts subarrays.