How do you solve Subarray Sum Equals K?

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.

What pattern does Subarray Sum Equals K use?

The Pattern: Hash Maps (Prefix Sum Frequency Counting) The Heuristic: 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.

Subarray Sum Equals K — Hash Maps

Q: What is the time complexity of Subarray Sum Equals K?

O(n). The algorithm iterates through the array once, performing O(1) hash map operations per element, resulting in linear time complexity.

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

Input: nums = [1,1,1], k = 2

Output: 2

For 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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class Solution:
  def subarraySum(self, nums: List[int], k: int) -> int:
      prefix_sum = 0
      ans = 0
      count = {0: 1}
6
      for num in nums:
          prefix_sum += num
          need = prefix_sum - k
          ans += count.get(need, 0)
          count[prefix_sum] = count.get(prefix_sum, 0) + 1
12
      return ans

Step-by-Step Solution

1

Initialize Prefix Sum, Answer Counter, and Frequency Map

3prefix_sum = 0
4ans = 0
5count = {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.

2

Iterate Through nums, Update Prefix Sum and Count Valid Subarrays

To process each element, update the running prefix sum, and count how many subarrays ending at the current index sum to k.

3

Return the Total Count of Subarrays Summing to k

To output the final count of all continuous subarrays whose sum equals k after processing the entire array.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 10 Critical

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.

Line 5 Critical

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.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

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?

See the answer with Pro.

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

or drill a free problem

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`