Prefix Sum with Hash Map Patterns in Java

The prefix sum with hash map pattern is a powerful technique for solving array problems efficiently, particularly those involving subarrays with specific sum conditions or frequency counting scenarios.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that the input array will contain at least one element, or should we handle empty arrays?
2. Can the input array contain negative numbers, and if so, how should we handle them in our prefix sum calculations?
3. Should we return the indices of the subarray or just the length of the longest subarray with sum zero?
4. Can we modify the input array in-place, or do we need to preserve the original array?
5. What is the expected time complexity for this problem? Should we aim for O(n) or O(n²)?

Restatement of the problem: Given an array of integers, find the length of the longest contiguous subarray with a sum equal to zero.

Clarification of inputs, outputs, and constraints:

• Input: An array of integers (can contain positive, negative, or zero values)
• Output: The length of the longest contiguous subarray with sum zero
• Constraints:
  • Array can have up to 10⁵ elements (based on typical FAANG constraints)
  • Values can be any integer within the range of a 32-bit signed integer
  • We're looking for contiguous subarrays (not just any subset)

Assumptions made:

• The array is 0-indexed and contains at least one element
• We're looking for the maximum length of a contiguous subarray with sum zero, not all such subarrays
• We can modify the input array in-place if needed (but prefer immutable approach for clarity)

Data shape and hidden structure: The problem exhibits the classic "subarray with sum zero" pattern, which is a variation of prefix sum problems. The key insight is that if we compute prefix sums and find two positions where the same prefix sum occurs, then the subarray between those positions has a sum of zero. This creates a hash map-based optimization opportunity where we can store the first occurrence of each prefix sum value and calculate the maximum length when we encounter a repeated value.

This pattern frequently appears in coding interviews as it tests understanding of:

• Prefix sum techniques
• Hash map usage for O(1) lookups
• Subarray manipulation and index tracking
• Optimization from brute force to linear time

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern is Prefix Sum with Hash Map. This pattern emerges when we need to efficiently count subarrays with a specific sum or find subarrays that meet certain criteria based on cumulative sums.

Wording that signals the pattern

Key indicators in the problem statement include:

• "subarray" - suggests we're looking at contiguous elements
• "sum of subarrays" - indicates cumulative sum operations are relevant
• "count" - suggests we need to track occurrences efficiently
• "target sum" - implies we're looking for specific sum values

Why this problem fits that pattern

This problem fits the prefix sum with hash map pattern because:

1. We're dealing with subarrays (contiguous elements)
2. The problem asks for counting subarrays with a specific sum property
3. We can leverage the mathematical relationship: sum[i:j] = prefixSum[j] - prefixSum[i-1]
4. Using a hash map to store frequency of prefix sums allows O(1) lookup for previous sums

Core insight needed to solve it

The core insight is that instead of checking all possible subarrays (which would be O(n²)), we can use the mathematical property that sum[i:j] = prefixSum[j] - prefixSum[i-1]. This means we want to count how many times prefixSum[j] - target has occurred before, which can be efficiently tracked using a hash map storing prefix sum frequencies.

This transforms the problem from checking all O(n²) subarrays to a single pass with O(1) lookups, reducing complexity from O(n²) to O(n).

3. Approach Evolution

My first instinct is to use a brute force approach where I check every possible subarray to see if it sums to zero. This would involve nested loops checking all subarrays starting from each index, which is O(n²) time complexity because for each starting position, I might need to check all ending positions. But that's inefficient and not optimal for large inputs.

Let me think about how to optimize this. I notice that if we're looking for subarrays that sum to zero, there's a mathematical property here: if the cumulative sum at position i equals the cumulative sum at position j, then the subarray between i+1 and j must sum to zero. This is because the difference between two cumulative sums gives us the sum of elements in between.

I notice that if I maintain a running prefix sum and use a hash map to store the first occurrence of each prefix sum value, I can reduce this to O(n) time. When I encounter a prefix sum that I've seen before, it means there's a subarray with sum zero between the previous occurrence and current position.

The key insight is that instead of checking all subarrays, I can leverage the relationship between prefix sums and subarray sums. For any subarray from index i to j, its sum equals (prefixSum[j] - prefixSum[i-1]). If this sum is zero, then prefixSum[j] = prefixSum[i-1].

This approach works because:

1. We're essentially looking for duplicate prefix sums
2. When we find a prefix sum that has been seen before, we know there's a zero-sum subarray
3. We only need to track the first occurrence of each prefix sum to get the longest valid subarray

The invariant that must hold is: at any point in the iteration, the hash map contains all prefix sums from indices 0 to current index, with their first occurrence positions. When we find a duplicate prefix sum, we know the subarray between the first occurrence and current position sums to zero.

This optimization reduces the time complexity from O(n²) to O(n) while maintaining O(n) space complexity for the hash map. The solution is optimal because we need to examine each element at least once to determine if any subarray sums to zero.

4. Data Structure Choice

For this prefix sum with hash map problem, I'll use a HashMap to store prefix sums and their frequencies.

Primary Data Structures:

• HashMap<Integer, Integer> - stores the frequency of each prefix sum encountered so far
  • Key: prefix sum value
  • Value: how many times this prefix sum has been seen
  • Why needed: allows O(1) lookup and update operations for prefix sum frequencies
  • Time impact: O(1) average for get/put operations
  • Space impact: O(n) in worst case where all prefix sums are unique

Why this choice is optimal: The hash map enables us to efficiently track how many times each prefix sum has occurred, which is essential for counting subarrays with a specific sum. Without it, we'd need to scan all previous prefix sums for each new position, leading to O(n²) time complexity.

Helper structures:

• No additional helper structures needed beyond the HashMap
• The solution maintains a running prefix sum as we iterate through the array

This is the most appropriate data structure because:

1. It provides constant-time access to prefix sum frequencies
2. It naturally handles the accumulation pattern required for prefix sum problems
3. It's well-suited for the "count of subarrays with sum K" pattern where we need to find how many previous prefix sums differ by exactly the target value

The HashMap is the key enabler that transforms this from a quadratic to linear time solution.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

Consider input array: [1, 2, 3, -1, -2, 4] with target sum k = 3

Step 1: Initialize prefixSum = 0, count = 0, and sumMap = {0:1} (base case)

Step 2: Process element 1:

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

Step 3: Process element 2:

• prefixSum = 1 + 2 = 3
• Check if prefixSum - k = 3 - 3 = 0 exists in map → Yes (from base case)
• Increment count: count = 0 + 1 = 1
• Add current prefix sum to map: sumMap = {0:1, 1:1, 3:1}
• Found first subarray [1,2] with sum 3

Step 4: Process element 3:

• prefixSum = 3 + 3 = 6
• Check if prefixSum - k = 6 - 3 = 3 exists in map → Yes (from previous step)
• Increment count: count = 1 + 1 = 2
• Add current prefix sum to map: sumMap = {0:1, 1:1, 3:1, 6:1}
• Found second subarray [1,2,3] with sum 3

Step 5: Process element -1:

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

Step 6: Process element -2:

• prefixSum = 5 + (-2) = 3
• Check if prefixSum - k = 3 - 3 = 0 exists in map → Yes (from base case)
• Increment count: count = 2 + 1 = 3
• Add current prefix sum to map: sumMap = {0:1, 1:1, 3:1, 6:1, 5:1, 3:2}
• Found third subarray [1,2,3,-1,-2] with sum 3

Step 7: Process element 4:

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

Final result: count = 3 subarrays with sum equal to target k = 3

The key insight is that when we find a prefix sum S such that S - k already exists in our map, it means there's a subarray ending at current position with sum exactly k. This works because if prefixSum[i] - prefixSum[j] = k, then prefixSum[i] - k = prefixSum[j].

The algorithm correctly handles all edge cases including negative numbers, and maintains the invariant that sumMap always contains prefix sums seen so far with their frequencies.

6. Java Solution

import java.util.*;

public class Solution {
    public int subarraySum(int[] nums, int k) {
        // HashMap to store frequency of prefix sums
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        
        // Initialize with sum 0 occurring once (empty subarray)
        prefixSumCount.put(0, 1);
        
        int result = 0;
        int currentSum = 0;
        
        for (int num : nums) {
            // Update running sum
            currentSum += num;
            
            // Check if (currentSum - k) exists in map
            // If yes, it means there are subarrays ending at current position with sum k
            int targetSum = currentSum - k;
            if (prefixSumCount.containsKey(targetSum)) {
                result += prefixSumCount.get(targetSum);
            }
            
            // Add current sum to map (increment frequency)
            prefixSumCount.put(currentSum, 
                prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }
        
        return result;
    }
}

This solution uses the prefix sum technique with a hash map to efficiently count subarrays that sum to k. The key insight is that if we have a prefix sum at index i and we want subarrays ending at i with sum k, we need to find how many previous prefix sums equal (currentSum - k). The hash map allows us to look up these counts in O(1) time rather than checking all previous sums.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes a single pass through the input array, processing each element exactly once. For each element, we perform constant-time operations: computing the running sum, checking if a prefix sum exists in our hash map, and updating the hash map. Since we process n elements with O(1) work per element, the overall time complexity is O(n).

Space Complexity: O(min(n, k)) where k is the target sum

In the worst case, our hash map could store up to n entries (when no valid subarrays exist), but in practice, it will only store the necessary prefix sums to detect valid subarrays. The hash map stores at most the number of distinct prefix sums we need to track, which is bounded by the range of possible prefix sums relative to our target.

The space complexity is dominated by the hash map storage, which can grow at most to the number of unique prefix sums that differ from our target by a value that exists in the array. In the best case where we find a valid subarray early, space usage is minimal.

Why these bounds are correct:

The O(n) time bound is tight because we must examine each element at least once to determine if any subarray sums to our target. The hash map operations (get/put) are O(1) amortized, making the linear scan the bottleneck.

The space bound is optimal because we only store prefix sums that are relevant to finding subarrays that sum to the target. We never store more than what's necessary to maintain our invariant: "if we've seen a prefix sum that equals (current_sum - target), then there exists a subarray ending at current position with sum equal to target."

This solution is optimal for the problem as stated, achieving linear time and space complexity that matches the theoretical lower bound for this type of subarray sum problem.

8. Edge Cases & Pitfalls

Edge cases that require careful handling:

Empty input and single element arrays:

• Empty array should return 0 (no subarrays with sum 0)
• Single element array needs special handling - if element is 0, return 1; otherwise return 0

Zero sum subarrays:

• Arrays with elements that sum to zero but don't start at index 0
• Example: [1, -1, 2, -2] has subarrays [1,-1] and [2,-2] with sum 0

Duplicate prefix sums:

• When multiple prefix sums are equal, we must count all occurrences
• This is why we store counts in the HashMap rather than just existence

Negative numbers and mixed signs:

• Negative numbers can create valid zero-sum subarrays when combined with positive numbers
• The algorithm must properly handle cases like [2, -1, -1, 0]

HashMap key collisions:

• Java's HashMap handles this internally with proper hash functions
• No special handling needed for this specific problem

Boundary conditions:

• When prefix sum equals target (0) at index 0, we must count that as a valid subarray
• The initial prefix sum of 0 at index -1 is crucial for correct counting

Common implementation pitfalls:

1. Incorrect initialization: Forgetting to add initial entry (0, 1) to the HashMap
2. Off-by-one errors: Miscounting subarrays due to incorrect index handling
3. Not accounting for prefix sum 0: Missing the case where a subarray from index 0 to i sums to 0
4. HashMap value updates: Incorrectly updating counts instead of properly incrementing them

The key insight is that we must handle the case where a prefix sum equals our target (0) at index 0, which requires the initial entry of (0, 1) to properly count subarrays starting from index 0.

9. Alternative Approaches

There are several alternative approaches to solving this problem, each with different trade-offs:

Brute Force Approach: The most straightforward alternative is to check every possible subarray using nested loops. For each starting index, we would calculate the sum of all subarrays beginning at that index and check if any equals the target. This approach has O(n³) time complexity due to nested loops and sum calculation, making it inefficient for large inputs. While simple to implement, it's not scalable.

Two Pointers with Sliding Window: This approach works well when we're looking for subarrays with specific sum properties, particularly when all elements are positive. We could maintain a sliding window and adjust its bounds based on whether the current sum is less than or greater than target. However, this approach fails when negative numbers are present because we can't determine whether to expand or shrink the window based on sum comparisons alone.

Binary Search with Prefix Sums: If we can preprocess all prefix sums and store them in a sorted array, we could use binary search to find if (current_prefix_sum - target) exists in the prefix sums. This approach would have O(n log n) time complexity but requires additional space for storing sorted prefix sums and is more complex to implement correctly.

Hash Map with Running Sum: Our chosen solution using hash map with prefix sums is optimal for this problem. The hash map approach provides O(n) time and space complexity, making it the most efficient solution for this specific constraint set.

The hash map approach is preferred because it maintains linear time complexity while effectively handling negative numbers and providing clean, readable code structure that's easy to debug and maintain in production environments.

10. Test Cases

public class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);
        
        int result = 0;
        int prefixSum = 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

int[] nums = {1, 1, 1};
int k = 2;
// Expected: 2
// Subarrays: [1,1] at indices 0-1 and [1,1] at indices 1-2

Case 2: Negative numbers

int[] nums = {1, -1, 0, 1};
int k = 1;
// Expected: 4
// Subarrays: [1], [-1,0,1], [1,-1,0,1], [1]

Case 3: Single element matching

int[] nums = {5};
int k = 5;
// Expected: 1
// Subarray: [5]

Case 4: No matching subarrays

int[] nums = {1, 2, 3};
int k = 7;
// Expected: 0
// No subarrays sum to 7

Case 5: Empty array

int[] nums = {};
int k = 0;
// Expected: 0
// No subarrays possible

Case 6: All zeros

int[] nums = {0, 0, 0};
int k = 0;
// Expected: 6
// All possible subarrays sum to 0

Case 7: Large numbers

int[] nums = {100, -100, 50, -50};
int k = 0;
// Expected: 4
// Subarrays: [100,-100], [50,-50], [100,-100,50,-50], [0]

These test cases cover various scenarios including positive/negative numbers, zero values, edge cases with empty arrays, and boundary conditions that stress the algorithm's correctness.

11. Final Summary

The core insight is that we can efficiently solve the subarray sum problem by leveraging the prefix sum technique with a hash map to store previously seen prefix sums, allowing us to find any subarray with the target sum in linear time. This approach works because if we've seen a prefix sum that equals our current prefix sum minus the target, then the subarray between those indices must sum to our target. The solution is optimal with O(n) time and space complexity, making it ideal for large input sizes where brute force approaches would be prohibitively expensive.

The key innovation is recognizing that instead of checking all possible subarrays (O(n²)), we can maintain a running prefix sum and use the mathematical relationship: if prefix[i] - prefix[j] = target, then prefix[i] = prefix[j] + target. This transforms the problem from a quadratic search into a linear lookup using hash map's O(1) average-case retrieval.