Meta — Subarray Sum Equals K (Prefix Sum + HashMap)

Problem Statement#

Given an integer array nums and an integer k, return the total number of subarrays whose sum equals k.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7
• Array may contain negative numbers

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

Input:  nums = [1, 2, 3], k = 3
Output: 2  (subarrays [1,2] and [3])

Why This Problem Matters#

Subarray Sum Equals K (LeetCode 560) is one of Meta's most-asked medium problems across phone screens and onsite rounds. Meta uses it to test whether candidates understand prefix sums and the complement lookup trick — a pattern that reduces O(N^2) brute-force solutions to O(N). This exact optimization shows up in Meta's feed ranking, where cumulative engagement scores are compared across time windows.

The naive solution checks all O(N^2) subarrays and sums each in O(N) — O(N^3) total. Prefix sums reduce the sum of any subarray to O(1), giving O(N^2). The hashmap takes it to O(N): at each index, ask "how many times has prefix_sum - k appeared before?" If that count is C, then there are C subarrays ending here that sum to k.

The crucial detail that trips up candidates: this problem allows negative numbers, so sliding window does not work. The prefix sum + hashmap approach handles negatives correctly.

The Core Insight#

Define prefix[i] = nums[0] + ... + nums[i]. A subarray nums[j..i] sums to k when prefix[i] - prefix[j-1] = k, or equivalently prefix[j-1] = prefix[i] - k.

As we scan left to right computing running prefix sums, we ask: "how many previous prefix sums equal current_prefix - k?" A hashmap stores the frequency of each prefix sum seen. Increment the answer by freq[current_prefix - k], then increment freq[current_prefix].

Initialize freq = {0: 1} to handle subarrays starting from index 0.

Visual Dry Run#

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

Result: 2

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def subarraySum(self, nums: list, k: int) -> int:
        freq = defaultdict(int)
        freq[0] = 1  # empty prefix
        prefix_sum = 0
        count = 0
 
        for num in nums:
            prefix_sum += num
            count += freq[prefix_sum - k]
            freq[prefix_sum] += 1
 
        return count

var subarraySum = function(nums, k) {
    const freq = new Map();
    freq.set(0, 1);
    let prefixSum = 0;
    let count = 0;
 
    for (const num of nums) {
        prefixSum += num;
        count += (freq.get(prefixSum - k) || 0);
        freq.set(prefixSum, (freq.get(prefixSum) || 0) + 1);
    }
 
    return count;
};

Time: O(N) — single pass through the array with O(1) hashmap operations Space: O(N) — hashmap stores at most N+1 distinct prefix sums

Common Mistakes#

• Forgetting to initialize freq[0] = 1 — misses subarrays starting from index 0
• Looking up freq[prefix_sum - k] after incrementing freq[prefix_sum] — double-counts same-index pairs
• Using sliding window (only works for positive numbers) — fails on negative values
• Confusing "count subarrays" with "find one subarray" — different output expectations
• Not handling k=0 correctly — subarrays summing to zero are valid and counted by the same formula

Interview Tips#

• Draw the prefix sum formula before coding: sum(j..i) = prefix[i] - prefix[j-1]
• Explain why sliding window fails: negative numbers mean shrinking left does not always decrease the sum
• The order of operations matters: look up freq[prefix_sum - k] BEFORE updating freq[prefix_sum]
• Meta specifically tests that you know this is O(N) — mention it explicitly
• Ask "can nums contain negatives?" to signal awareness; this rules out sliding window

Follow-up Questions#

• What if you need to find one subarray with sum k? — Same approach, store index instead of frequency
• What if you need the longest subarray with sum k? — Track earliest index of each prefix sum
• What if nums contains only positives? — Sliding window works; but prefix+map also works
• How do you count subarrays with sum at most k? — Binary search on prefix sums for each right endpoint
• What is the number of subarrays with sum divisible by k? — Use prefix_sum % k as the key

Key Takeaways#

• The key equation: sum(j..i) = prefix[i] - prefix[j-1], so look for prefix[j-1] = prefix[i] - k
• Initialize the hashmap with {0: 1} to correctly count subarrays starting at index 0
• Always look up the complement BEFORE inserting the current prefix sum — order prevents self-counting
• Sliding window fails for arrays with negative numbers; prefix sum + hashmap handles all cases
• Meta tests this to verify O(N) optimization intuition — brute force O(N^2) or O(N^3) will not pass
• Time O(N) and space O(N); the hashmap is the only extra structure
• The same pattern solves: subarray sum divisible by k, longest subarray with sum k, and 2D submatrix sum problems