Prefix Sum with Hash Maps for Subarray Problems

Prefix sum with hash maps is a powerful technique for solving subarray problems efficiently, enabling O(n) time complexity for range sum queries and subarray counting through clever use of cumulative sums and hash table lookups.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array will contain only integers, or could it include floats/different numeric types?
2. Do we need to handle cases where the input array is empty or has only one element?
3. Should we return all valid subarrays that sum to zero, or just the count of such subarrays?
4. Can we modify the input array in-place, or must we preserve it?
5. What is the expected time complexity for the follow-up? Should we aim for O(n) or can we accept O(n log n)?

Restate the pattern or problem type in your own words: This pattern involves efficiently finding subarrays with specific properties (like sum to zero) using prefix sums combined with hash maps. The key idea is to compute cumulative sums and use a hash map to store previously seen prefix sums, enabling us to detect when a subarray sum equals zero in linear time.

Clarify the signal words and constraint shape that point to it:

• Signal words: "subarray," "sum to zero," "equal sum," "contiguous elements"
• Constraint shape: Need to find contiguous subarrays with specific sum properties, often involving zero or target sum
• Common in problems like "Subarray Sum Equals K" or "Find Subarray with Zero Sum"

Note any assumptions you are making:

• The input array contains numeric values (integers or floats)
• We're looking for contiguous subarrays
• The problem is asking for either count or actual subarrays matching criteria

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is primarily designed for static input scenarios where all data is available upfront. It's not naturally suited for streaming or online processing because it requires knowledge of the entire input to build prefix sums and hash maps. For streaming scenarios, we'd need a different approach like sliding window or maintaining running statistics with additional constraints.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Subarray sum equals target" or "find subarray with sum K"
• "Number of subarrays with sum equal to K"
• "Contiguous subarray with specific property"
• Arrays with both positive and negative numbers
• Problems asking for count of subarrays with specific sum conditions

Why this pattern fits better than alternatives: The prefix sum with hash map approach is superior to brute force because it reduces time complexity from O(n²) to O(n). Unlike sliding window techniques that require all positive numbers, this pattern works with negative numbers by leveraging the mathematical property that if prefix[i] - prefix[j] = target, then the subarray from index j+1 to i has sum equal to target.

When variations apply:

• For problems where we need to find subarrays with sum exactly K, use prefix sum with hash map
• For range sum queries with updates, consider segment trees or Fenwick trees instead
• When only positive numbers and range sum queries are needed, sliding window might be more intuitive but not as general

Core insight: The key insight is that we can transform the subarray sum problem into a two-sum-like problem where we look for previous prefix sums that differ by the target value. By storing prefix sums in a hash map, we can quickly check if a required previous prefix sum exists.

This pattern is particularly effective when:

1. We're counting subarrays with specific sum properties
2. The array contains negative numbers (sliding window won't work)
3. We want optimal O(n) time complexity
4. The problem asks for count rather than actual subarrays

3. Approach Evolution

Interview communication script:

"My first instinct is to solve this with a brute force approach where I check every possible subarray and calculate its sum, but that's O(n²) because for each starting position, I'd have to iterate through all ending positions. Let me think about how to optimize this...

I notice that if I'm looking for subarrays with a specific sum, there's a mathematical relationship here. If I know the prefix sum up to index j and I want to find subarrays ending at j with a target sum, I can look for prefix sums that are exactly (current_prefix_sum - target_sum). This suggests using a hash map to store prefix sums I've seen so far.

If I maintain a running sum and use a hash map to store how many times each prefix sum has occurred, then for any current position, I can quickly look up how many previous prefix sums would form valid subarrays ending at this position. This reduces the time complexity from O(n²) to O(n) by avoiding nested loops.

The key insight is that instead of checking all subarrays, I can use the relationship: if prefix[j] - prefix[i] = target_sum, then prefix[i] = prefix[j] - target_sum. So for each position, I just need to count how many times (current_prefix - target_sum) has appeared before."

Brute-force approach and why it is not ideal:

The brute force approach would involve checking every possible subarray by computing the sum of each subarray explicitly. For an array of size n, we would have n(n+1)/2 subarrays to check, each requiring up to O(n) time to compute the sum. This results in O(n³) time complexity in the worst case, which is inefficient for large inputs.

Improved approach and the key optimization:

The key optimization uses prefix sums with a hash map. Instead of recalculating subarray sums repeatedly, we maintain a running prefix sum and use a hash map to store the frequency of each prefix sum encountered so far. For any position, we can quickly determine how many previous subarrays ending at this position have the desired sum by looking up (current_prefix_sum - target_sum) in our hash map.

Final approach with step-by-step reasoning:

1. Initialize a hash map to store prefix sum frequencies, with an initial entry for sum 0 (representing empty prefix)
2. Iterate through the array, maintaining a running prefix sum
3. For each position, calculate what previous prefix sum would be needed to form a valid subarray with target sum
4. Look up this required prefix sum in our hash map to count valid previous subarrays
5. Update the hash map with the current prefix sum frequency

Important invariants that must hold:

• The hash map always contains the frequency count of all prefix sums seen so far
• At each step, we're counting subarrays that end at the current position
• The initial entry of 0 in the hash map handles cases where a subarray starting from index 0 has the target sum
• The prefix sum relationship ensures we don't double-count or miss valid subarrays

4. Data Structure Choice

For prefix sum with hash map approach, the primary data structures are:

HashMap<Integer, Integer> - This is the core data structure that stores the frequency of each prefix sum encountered so far. The key represents the prefix sum value, and the value represents how many times that prefix sum has been seen. This allows O(1) lookup and update operations for maintaining the count of prefix sums.

Array/ArrayList - The input array itself is used to compute running prefix sums. In most implementations, we iterate through the array once while maintaining a cumulative sum.

Why HashMap is preferred over other structures:

• Unlike arrays or lists for storing prefix sums, HashMap provides O(1) average time complexity for both lookups and insertions
• It handles arbitrary prefix sum values efficiently without requiring pre-allocation of memory for all possible sums
• It naturally handles negative prefix sums and large ranges without index mapping complications

Time and Space Impact:

• Time: O(n) for building the HashMap where n is array length
• Space: O(min(n, k)) where k is the number of unique prefix sums (worst case O(n) when all prefix sums are distinct)
• The space complexity is bounded by the number of unique prefix sums, which can be at most n in worst case

Helper structures:

• No additional helper structures are needed beyond the HashMap for basic prefix sum problems
• The input array is used in-place for computing running sums
• A single variable prefixSum is maintained to track current cumulative sum

This choice enables the algorithm to efficiently count subarrays with target sum by leveraging the mathematical property that if prefix[i] - prefix[j] = target, then the subarray from index j+1 to i has sum equal to target.

5. Algorithm Walkthrough

Let me trace through the algorithm using the example nums = [1, 2, 3, -3, 4] with target sum k = 3.

Step 1: Initialize prefixSum = 0, count = 0, and sumMap = {0: 1} (empty prefix).

Step 2: Process nums[0] = 1:

• prefixSum = 0 + 1 = 1
• We want to find if there exists a previous prefix sum such that currentSum - previousSum = k
• So we check if 1 - 3 = -2 exists in map → No
• Add current prefix sum to map: sumMap = {0: 1, 1: 1}
• count = 0

Step 3: Process nums[1] = 2:

• prefixSum = 1 + 2 = 3
• Check if 3 - 3 = 0 exists in map → Yes, count = 1
• Increment count = 1
• Add current prefix sum to map: sumMap = {0: 1, 1: 1, 3: 1}
• count = 1

Step 4: Process nums[2] = 3:

• prefixSum = 3 + 3 = 6
• Check if 6 - 3 = 3 exists in map → Yes, count = 1
• Increment count = 2
• Add current prefix sum to map: sumMap = {0: 1, 1: 1, 3: 1, 6: 1}
• count = 2

Step 5: Process nums[3] = -3:

• prefixSum = 6 + (-3) = 3
• Check if 3 - 3 = 0 exists in map → Yes, count = 2
• Increment count = 3
• Add current prefix sum to map: sumMap = {0: 1, 1: 1, 3: 1, 6: 1, 3: 2}
• count = 3

Step 6: Process nums[4] = 4:

• prefixSum = 3 + 4 = 7
• Check if 7 - 3 = 4 exists in map → No
• Add current prefix sum to map: sumMap = {0: 1, 1: 1, 3: 1, 6: 1, 3: 2, 7: 1}
• count = 3

Final result: The algorithm returns count = 3 because there are three subarrays with sum equal to 3: [1,2], [1,2,3,-3], and [3].

The key insight is that when we're at index i with prefix sum S_i, we look for any previous prefix sum S_j such that S_i - S_j = k. This means we're looking for S_j = S_i - k in our map, which tells us how many subarrays ending at index i have sum k. The map maintains counts of all prefix sums we've seen so far, enabling O(1) lookup.

Edge cases are handled naturally:

• Empty arrays return 0
• Negative numbers work because we're tracking cumulative sums
• Duplicate prefix sums correctly contribute to multiple valid subarrays

6. Java Solution

import java.util.*;

public class SubarraySumEqualsK {
    /**
     * Find the number of subarrays that sum to k using prefix sum with hash map
     * Time: O(n), Space: O(n)
     */
    public int subarraySum(int[] nums, int k) {
        // Map to store frequency of prefix sums
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        
        // Initialize with sum 0 having frequency 1 (empty prefix)
        prefixSumCount.put(0, 1);
        
        int prefixSum = 0;
        int result = 0;
        
        for (int num : nums) {
            // Update running prefix sum
            prefixSum += num;
            
            // Check if (prefixSum - k) exists in map
            // If yes, it means there are subarrays ending at current position with sum k
            int target = prefixSum - k;
            if (prefixSumCount.containsKey(target)) {
                result += prefixSumCount.get(target);
            }
            
            // Add current prefix sum to map (increment frequency)
            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return result;
    }
}

The solution uses the mathematical property that if we have a prefix sum at index i and we want to find subarrays ending at i with sum k, we need to check if (prefixSum[i] - k) has occurred before. This is because if prefixSum[j] = prefixSum[i] - k, then the subarray from j+1 to i has sum k.

The key insight is that we maintain a hash map of prefix sums and their frequencies, allowing us to count valid subarrays in linear time. We initialize with sum 0 having frequency 1 to handle cases where a subarray starting from index 0 has the target sum.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array, performing constant-time operations at each step. For each element, we:

• Compute a running prefix sum (O(1))
• Check if prefixSum - k exists in the hash map (O(1) average case)
• Update the hash map with the current prefix sum (O(1) average case)

Since each operation inside the loop is O(1), and we iterate through n elements, the overall time complexity is O(n).

Space Complexity: O(min(n, m)) where n is the length of the input array and m is the number of distinct prefix sums encountered.

In the worst case, we might store all prefix sums in our hash map, requiring O(n) space. However, if there are fewer distinct prefix sums than array elements (which happens when many prefix sums are equal or cancel out), the space usage is bounded by the number of unique prefix sums.

The hash map stores at most one entry per unique prefix sum, and in the best case where many prefix sums are identical or cancel out, we can have significantly fewer entries than n elements.

The solution is optimal for this problem because:

1. We must examine each element at least once to determine valid subarrays
2. The hash map lookup provides the best possible O(1) access for checking previous prefix sums
3. No better data structure exists that would reduce the fundamental O(n) requirement for processing all elements

This is near-optimal because any correct solution must process all n elements at least once, and we've achieved the best possible time complexity for this operation.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: The solution correctly handles empty arrays by returning 0, as there are no subarrays to consider.
• Single element array: When k = 0, a single element equals the target sum, so we return 1. When k ≠ 0, we must ensure that the element itself doesn't contribute to a valid subarray.

Duplicate Values and Repeated States

• Duplicate prefix sums: Multiple prefix sums can have the same value, which is handled correctly by storing all indices in a HashMap or using a counter.
• Zeroes in the array: When elements are zero, they do not change the prefix sum but can still contribute to valid subarrays. The algorithm correctly accounts for these.

Boundary Conditions

• Array with all zeros: When k = 0, every subarray sum is zero, so we count all possible subarrays. The solution correctly handles this case.
• Negative numbers: Negative numbers can cause prefix sums to decrease, but the algorithm still works by maintaining the hash map of prefix sum frequencies.
• Prefix sum equals k: When a prefix sum directly equals k, it contributes one valid subarray from index 0 to current index.

Common Implementation Mistakes

• Incorrect initialization: Not initializing the hash map with {0: 1} can lead to missing subarrays starting from index 0.
• Index tracking: Incorrectly managing the indices in the hash map can cause missing or double-counting subarrays.
• HashMap key handling: Using sum - k as a key instead of sum can lead to incorrect lookups.
• Off-by-one errors: Miscounting subarrays due to incorrect loop bounds or index calculations.

// Example edge case handling:
// Input: nums = [0, 0, 0], k = 0
// Expected: 6 subarrays (all combinations of indices)
// Without proper initialization, we might miss some valid subarrays

9. Alternative Approaches

There are several alternative approaches to solving problems that can be solved with prefix sum and hash maps, each with their own trade-offs:

Brute Force Approach: For problems like "Subarray Sum Equals K", we could check every possible subarray using nested loops. This would be O(n³) time complexity for finding all subarrays and O(1) space. While this works for small inputs, it's inefficient for larger datasets and doesn't scale well.

Two Pointers with Sliding Window: For problems where we're looking for subarrays with specific properties (like sum equals target), we could use a sliding window technique if the array has certain characteristics like all positive numbers. However, this approach fails when dealing with negative numbers or when we need to find all occurrences rather than just one valid subarray.

Segment Tree / Fenwick Tree: For dynamic range sum queries or updates, we might consider segment trees or Fenwick trees. These provide O(log n) query and update operations but come with higher constant factors and more complex implementation compared to the hash map approach.

Prefix Sum with Array: Instead of using a HashMap for storing prefix sums, we could use an array-based approach if the range of possible prefix sums is small and known. This trades space efficiency for potentially faster access times, but only works in very specific constrained scenarios.

The hash map approach is preferred because it provides optimal time complexity O(n) with clean, readable code that handles negative numbers gracefully. It's particularly effective when we're looking for the count of subarrays with a specific sum or when we need to find all occurrences rather than just one valid solution.

10. Test Cases

public class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);
        int prefixSum = 0;
        int result = 0;
        
        for (int num : nums) {
            prefixSum += num;
            int target = prefixSum - k;
            if (prefixSumCount.containsKey(target)) {
                result += prefixSumCount.get(target);
            }
            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return result;
    }
}

Sample Test Cases

Case 1: Basic positive case

• Input: nums = [1, 1, 1], k = 2
• Expected: 2
• Explanation: Subarrays [1,1] at indices 0-1 and [1,1] at indices 1-2 both sum to 2

Case 2: Negative numbers

• Input: nums = [1, -1, 0], k = 0
• Expected: 3
• Explanation: Subarrays [1,-1], [0], and [1,-1,0] all sum to 0

Case 3: Single element matching target

• Input: nums = [5], k = 5
• Expected: 1
• Explanation: The entire array sums to 5

Case 4: No valid subarrays

• Input: nums = [1, 2, 3], k = 7
• Expected: 0
• Explanation: No contiguous subarray sums to 7

Case 5: Empty array

• Input: nums = [], k = 0
• Expected: 0
• Explanation: No elements to form subarrays

Case 6: All zeros

• Input: nums = [0, 0, 0], k = 0
• Expected: 6
• Explanation: All possible subarrays sum to 0 (3 single elements + 2 two-element + 1 three-element)

11. Final Summary

The core idea is to leverage prefix sums combined with hash map lookups to efficiently count subarrays with a target sum by transforming the problem into finding pairs of prefix sums that differ by the target value. This solution works because it reduces the two-sum-like subarray problem to a single-pass hash map lookup, achieving optimal O(n) time complexity. The key insight is that if we maintain a running sum and store prefix sums in a hash map, we can instantly determine how many previous subarrays end at the current position with the desired sum, making this approach both elegant and highly efficient for the subarray sum counting problem.