Subarray Sum Equals K

Subarray Sum Equals K

What is this problem about?

"Subarray Sum Equals K" is a medium-difficulty problem that asks you to find the total number of continuous subarrays whose sum equals a target value k. Unlike the "product" version, this problem often involves negative numbers, which makes a simple sliding window approach impossible (since adding an element doesn't necessarily increase the sum). You are given an array of integers and must find the count of all matching subarrays.

Why is this asked in interviews?

This is one of the most frequently asked questions at companies like Meta, Amazon, and Google. It is a brilliant test of whether a candidate can use a Hash Map to store "prefix sums." It evaluates the ability to transform a subarray problem into a "sum of prefixes" problem, which is a key leap in algorithmic thinking. It separates those who rely on brute force from those who understand time-space trade-offs.

Algorithmic pattern used

The primary pattern for this coding problem is the Prefix Sum combined with a Hash Table. As you iterate through the array, you keep track of the cumulative sum (current_sum). If current_sum - k has been seen before as a prefix sum, it means there is a subarray that sums to k. You store the frequency of each prefix sum in a hash map to quickly look up how many times a particular sum has occurred.

Example explanation (use your own example)

Array: [1, 2, 3], k = 3.

1. Map: {0: 1} (to handle cases where the subarray starts at index 0).
2. Index 0: sum = 1. Check for (1 - 3 = -2) in map. Not found. Add {1: 1} to map.
3. Index 1: sum = 1 + 2 = 3. Check for (3 - 3 = 0) in map. Found (at 0)! Count = 1. Add {3: 1} to map.
4. Index 2: sum = 3 + 3 = 6. Check for (6 - 3 = 3) in map. Found (at 3)! Count = 1 + 1 = 2. Final result: 2. (The subarrays are [1, 2] and [3]).

Common mistakes candidates make

The most common mistake is forgetting to initialize the hash map with {0: 1}. This leads to missing subarrays that sum to k starting from the very beginning of the array. Another mistake is trying to use two pointers/sliding window when the array contains negative numbers. This fails because the window doesn't behave monotonically. Candidates also sometimes forget to store the frequency of the sums and instead only store a boolean, which fails when multiple prefix sums are the same.

Interview preparation tip

To master the Subarray Sum Equals K interview question, practice problems involving "Prefix Sums." Understand the core logic: Sum(i, j) = PrefixSum(j) - PrefixSum(i-1). This formula is the secret to many subarray problems. Be prepared to explain the O(n) time complexity and O(n) space complexity of your solution.