Subarray Sum Equals K
Problem
Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
- 1 ≤ nums.length ≤ 2 * 10⁴
- −1000 ≤ nums[i] ≤ 1000
- −10⁷ ≤ k ≤ 10⁷
Example
nums = [1,1,1], k = 22For nums = [1,1,1] and k = 2, the output is 2. Here is the step-by-step walkthrough: 1. Initialization Start with prefix_sum = 0 and a frequency map count = {0: 1}. The entry {0: 1} is critical as it allows us to detect subarrays that start at the very beginning of the array. 2. First Element (Value 1) The running prefix_sum becomes 1. We check for (prefix_sum - k), which is 1 - 2 = -1. This value is not in our map, so no valid subarray ends here. We then update the map: count[1] = 1. 3. Second Element (Value 1) The prefix_sum becomes 2. We check for 2 - 2 = 0. Our map contains 0 with frequency 1. This means we found one valid subarray (nums[0..1]). We add 1 to our answer and update the map: count[2] = 1. 4. Third Element (Value 1) The prefix_sum becomes 3. We check for 3 - 2 = 1. Our map contains 1 with frequency 1. This identifies the second valid subarray (nums[1..2]). We add 1 to our answer. Final Result: 2
Approach
Straightforward Solution
A brute-force approach enumerates all subarrays and sums their elements, resulting in O(n²) time complexity, which is inefficient for large inputs.
Core Observation
The sum of a continuous subarray nums[i..j] is the difference between two prefix sums: prefix_sum[j] - prefix_sum[i-1]. To find a subarray that sums to k, we set up the equation: prefix_sum[j] - prefix_sum[i-1] = k By rearranging this terms, we isolate what we need to find: prefix_sum[i-1] = prefix_sum[j] - k This implies that at any index j, we simply check our hash map to see how many times the specific sum (prefix_sum[j] - k) has occurred previously.
Path to Optimal
By maintaining a running prefix sum and a hash map that counts the frequency of each prefix sum encountered, the algorithm can, at each step, determine how many subarrays ending at the current index sum to k by looking up prefix_sum[j] - k in the map. This transforms the problem into a single pass with O(n) time complexity.
Optimal Approach
Iterate through nums, updating the prefix sum. For each prefix sum, check if prefix_sum - k exists in the hash map and add its frequency to the answer. Then update the hash map with the current prefix sum frequency. This approach guarantees O(n) time and O(n) space complexity.
Time
O(n)
The algorithm iterates through the array once, performing O(1) hash map operations per element, resulting in linear time complexity.
Space
O(n)
The hash map stores frequencies of prefix sums, which in the worst case can be up to n distinct sums, requiring linear auxiliary space.
Pattern Spotlight
Hash Maps (Prefix Sum Frequency Counting)
When searching for subarrays with a target sum, use prefix sums to convert the problem into finding pairs of prefix sums differing by k, and use a hash map to count frequencies of prefix sums for O(1) lookups.
Solution
| 1 | class Solution:
|
| 2 | def subarraySum(self, nums: List[int], k: int) -> int:
|
| 3 | prefix_sum = 0
|
| 4 | ans = 0
|
| 5 | count = {0: 1}
|
| 6 |
|
| 7 | for num in nums:
|
| 8 | prefix_sum += num
|
| 9 | need = prefix_sum - k
|
| 10 | ans += count.get(need, 0)
|
| 11 | count[prefix_sum] = count.get(prefix_sum, 0) + 1
|
| 12 |
|
| 13 | return ans |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int subarraySum(int[] nums, int k) { |
| 6 | int prefix_sum = 0; |
| 7 | int ans = 0; |
| 8 | Map<Integer, Integer> count = new HashMap<>(); |
| 9 | count.put(0, 1); |
| 10 | |
| 11 | for (int num : nums) { |
| 12 | prefix_sum += num; |
| 13 | int need = prefix_sum - k; |
| 14 | ans += count.getOrDefault(need, 0); |
| 15 | count.put(prefix_sum, count.getOrDefault(prefix_sum, 0) + 1); |
| 16 | } |
| 17 | |
| 18 | return ans; |
| 19 | } |
| 20 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int subarraySum(vector<int>& nums, int k) { |
| 9 | int prefix_sum = 0; |
| 10 | int ans = 0; |
| 11 | unordered_map<int, int> count; |
| 12 | count[0] = 1; |
| 13 | |
| 14 | for (int num : nums) { |
| 15 | prefix_sum += num; |
| 16 | int need = prefix_sum - k; |
| 17 | if (count.find(need) != count.end()) { |
| 18 | ans += count[need]; |
| 19 | } |
| 20 | count[prefix_sum]++; |
| 21 | } |
| 22 | |
| 23 | return ans; |
| 24 | } |
| 25 | }; |
| 1 | var subarraySum = function(nums, k) { |
| 2 | let prefix_sum = 0; |
| 3 | let ans = 0; |
| 4 | const count = new Map(); |
| 5 | count.set(0, 1); |
| 6 | |
| 7 | for (const num of nums) { |
| 8 | prefix_sum += num; |
| 9 | const need = prefix_sum - k; |
| 10 | ans += count.get(need) || 0; |
| 11 | count.set(prefix_sum, (count.get(prefix_sum) || 0) + 1); |
| 12 | } |
| 13 | |
| 14 | return ans; |
| 15 | }; |
Step-by-Step Solution
Initialize Prefix Sum, Answer Counter, and Frequency Map
| 3 | prefix_sum = 0
|
| 4 | ans = 0
|
| 5 | count = {0: 1}
|
Objective
To set up the initial state for prefix sum calculation and frequency tracking before iterating through the array.
Key Insight
Starting with prefix_sum = 0 and count = {0: 1} accounts for subarrays that begin at index 0 and sum to k. The frequency map stores how many times each prefix sum has occurred, enabling quick lookups to find valid subarrays.
Interview Quick-Check
Core Logic
Initializing count with {0: 1} is critical to handle subarrays starting at the beginning of the array.
Common Pitfalls & Bugs
Forgetting to initialize count with 0 sum frequency leads to missing subarrays that start at index 0.
Iterate Through nums, Update Prefix Sum and Count Valid Subarrays
| 7 | for num in nums:
|
| 8 | prefix_sum += num
|
| 9 | need = prefix_sum - k
|
| 10 | ans += count.get(need, 0)
|
| 11 | count[prefix_sum] = count.get(prefix_sum, 0) + 1
|
Objective
To process each element, update the running prefix sum, and count how many subarrays ending at the current index sum to k.
Key Insight
At each step, the algorithm calculates the needed prefix sum (prefix_sum - k) that would form a valid subarray with sum k ending at the current index. By adding the frequency of this needed prefix sum to the answer, it counts all such subarrays efficiently. Then it updates the frequency map with the current prefix sum for future lookups.
Interview Quick-Check
Core Logic
The key operation is checking count.get(prefix_sum - k, 0) to find how many previous prefix sums allow forming a subarray summing to k.
State & Boundaries
The prefix sum is updated cumulatively, and the frequency map is updated after counting to ensure correct counting of subarrays.
Common Pitfalls & Bugs
Updating the frequency map before counting can lead to counting subarrays incorrectly, including empty subarrays.
Return the Total Count of Subarrays Summing to k
| 13 | return ans |
Objective
To output the final count of all continuous subarrays whose sum equals k after processing the entire array.
Key Insight
After the single pass, the accumulated answer reflects the total number of valid subarrays, leveraging the prefix sum frequency counts to avoid redundant computations.
Interview Quick-Check
Core Logic
Returning ans after the loop completes provides the total count of all subarrays summing to k.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
ans += count.get(need, 0)Increment ans by the frequency of the needed prefix sum.
Adding count.get(need, 0) counts all subarrays ending at the current index whose sum equals k, leveraging the frequency map for O(1) lookup.
count = {0: 1}Initialize count dictionary with prefix sum zero frequency as one.
This initialization accounts for subarrays that start at index zero and sum exactly to k, ensuring these are counted correctly.
need = prefix_sum - kCalculate the needed prefix sum to form a subarray summing to k.
The value prefix_sum - k represents the prefix sum that, if previously seen, indicates a subarray ending at the current index sums to k.
count[prefix_sum] = count.get(prefix_sum, 0) + 1Update the frequency of the current prefix sum in the count map.
Recording the current prefix sum frequency enables future subarray sum checks and ensures accurate counting of overlapping subarrays.
prefix_sum = 0Initialize prefix_sum to zero to track cumulative sums.
Starting prefix_sum at zero allows the algorithm to accumulate sums from the beginning of the array, enabling calculation of subarray sums via differences of prefix sums.
prefix_sum += numAdd the current number to the running prefix sum.
Updating prefix_sum maintains the cumulative sum up to the current index, which is essential for calculating subarray sums via prefix sums.
return ansReturn the total count of subarrays summing to k.
After processing all elements, ans holds the total number of valid subarrays, completing the solution.
ans = 0Initialize ans to zero to count valid subarrays.
This variable accumulates the total number of subarrays found that sum to k, serving as the final output.
for num in nums:Iterate through each number in the input array.
Processing each element sequentially is necessary to build prefix sums and identify valid subarrays ending at each index.
Test Your Understanding
Why does checking for prefix_sum - k in the hash map correctly count the number of subarrays summing to k ending at the current index?
Because the difference between two prefix sums equals the sum of the subarray between their indices, so each occurrence of prefix_sum - k corresponds to a subarray ending at the current index with sum k.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Subarray Sum Equals K from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Subarray Sum Equals K drill