Subarray Sum Equals K: Optimal Coding Interview Solution

Some coding interview problems look simple until you try to solve them efficiently. Subarray Sum Equals K is one of those classics: given an integer array and a target value k, count how many continuous subarrays have a sum equal to k. The brute-force idea is easy to understand, but the optimal solution teaches a powerful technique that appears again and again in array, hash map, and prefix sum problems.

TLDR: The optimal solution uses prefix sums and a hash map to count subarrays in linear time. Instead of checking every possible subarray, we track how often each running sum has appeared. For each index, if currentSum – k has been seen before, those previous positions form valid subarrays ending at the current index. This gives an O(n) time solution with O(n) extra space.

Understanding the Problem

A subarray is a continuous portion of an array. For example, in the array [1, 2, 3], valid subarrays include [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3]. The goal is not to return the subarrays themselves, but to count how many of them add up to a given target k.

Consider this example:

• Input: nums = [1, 1, 1], k = 2
• Valid subarrays: [1, 1] at indices 0..1 and [1, 1] at indices 1..2
• Output: 2

At first glance, it may seem reasonable to generate every possible subarray and calculate its sum. However, that approach quickly becomes inefficient as the array grows.

The Brute-Force Approach

The most direct solution is to try every starting index and every ending index. For each pair, compute the sum and check whether it equals k.

count = 0

for start in range(n):
    sum = 0
    for end in range(start, n):
        sum += nums[end]
        if sum == k:
            count += 1

This version is better than recomputing each subarray sum from scratch because it keeps a running sum inside the inner loop. Still, it has a time complexity of O(n²). For small arrays, it works fine. For interview constraints where n may be tens or hundreds of thousands, it is not enough.

The key question becomes: Can we determine, at each position, how many valid subarrays end here without scanning all previous positions?

The Key Insight: Prefix Sums

A prefix sum is the sum of all elements from the beginning of the array up to a certain index. If we know the prefix sum at two positions, we can compute the sum of the subarray between them.

Suppose:

• prefix[j] is the sum of elements from index 0 to j
• prefix[i] is the sum of elements from index 0 to i

Then the sum of the subarray after i through j is:

prefix[j] - prefix[i]

We want that value to equal k:

prefix[j] - prefix[i] = k

Rearranging gives:

prefix[i] = prefix[j] - k

This equation is the heart of the optimal solution. At each position, we calculate the current prefix sum. Then we ask: How many previous prefix sums were equal to currentSum – k? Each one represents a valid subarray ending at the current index.

Why a Hash Map Solves It

To answer that question quickly, we use a hash map. The map stores:

• Key: a prefix sum value
• Value: how many times that prefix sum has occurred

As we move through the array, we maintain a running sum called currentSum. For every number:

1. Add the number to currentSum.
2. Compute needed = currentSum - k.
3. If needed exists in the map, add its frequency to the answer.
4. Record the current prefix sum in the map.

One important detail: initialize the map with {0: 1}. This handles subarrays that start at index 0. If the current prefix sum itself equals k, then currentSum - k is 0, and the initial zero prefix sum correctly counts that subarray.

Optimal Python Solution

def subarraySum(nums, k):
    prefix_count = {0: 1}
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num

        needed = current_sum - k
        if needed in prefix_count:
            count += prefix_count[needed]

        prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1

    return count

This is the standard interview-ready solution. It is concise, efficient, and handles positive numbers, negative numbers, and zeros without modification.

Walking Through an Example

Let’s use:

nums = [1, 2, 3]
k = 3

We start with:

• prefix_count = {0: 1}
• current_sum = 0
• count = 0

At the first number, 1, the current sum becomes 1. We need 1 - 3 = -2, which is not in the map. Store prefix sum 1.

At the second number, 2, the current sum becomes 3. We need 3 - 3 = 0, and 0 exists once in the map. That means the subarray [1, 2] sums to 3, so we increment the count.

At the third number, 3, the current sum becomes 6. We need 6 - 3 = 3, and 3 exists once. That corresponds to the subarray [3]. The final answer is 2.

Why Sliding Window Does Not Work Reliably

Many candidates try to solve this problem with a sliding window. That technique works well when all numbers are positive because expanding the window always increases the sum and shrinking it always decreases the sum. But this problem often allows negative numbers.

For example:

nums = [1, -1, 1]
k = 1

With negative numbers, the sum can rise or fall unpredictably. Expanding the window might decrease the sum, and shrinking it might increase the sum. This breaks the logic that makes sliding window reliable. Prefix sums, however, are unaffected by this issue because they compare accumulated totals rather than depending on monotonic movement.

Complexity Analysis

• Time Complexity: O(n), because we process each element once.
• Space Complexity: O(n), because the hash map may store up to n distinct prefix sums.

This is optimal for typical interview expectations. You cannot count all relevant subarrays without at least inspecting every element, so O(n) time is the best practical target.

Common Interview Pitfalls

• Forgetting to initialize the map with 0: 1: This causes missed subarrays that begin at index 0.
• Using a set instead of a frequency map: Duplicate prefix sums matter because each occurrence may form a different valid subarray.
• Updating the map too early: Check for currentSum - k before adding the current sum, or you may accidentally count invalid empty subarrays in certain cases.
• Assuming all numbers are positive: The presence of negative numbers is exactly why the prefix sum approach is so valuable.

Final Thoughts

Subarray Sum Equals K is more than a single LeetCode-style problem. It is a gateway to a broader pattern: using accumulated state plus a hash map to transform a nested-loop search into a linear scan. Once you understand why currentSum - k matters, the solution feels less like a trick and more like a reusable tool.

In an interview, explain the brute-force approach first, identify its inefficiency, then introduce prefix sums and the hash map. That progression shows clear problem-solving ability. The final code is short, but the idea behind it is powerful: sometimes the fastest way to find a subarray is not to search for the subarray directly, but to remember the sums that came before it.