Prefix Sum vs Hash Map: When You Need Both (And When You Don't)

You see "subarray sum." You think: "Do I need prefix sum? Hash map? Both?"

The answer depends on the problem type. Sometimes you need just one, sometimes both.

TL;DR

Prefix sum alone:

• Range queries with known indices
• Multiple queries on static array

Hash map alone:

• Two Sum (no prefix sum needed)
• Finding pairs

Both together:

• Subarray sum equals k
• Counting subarrays with condition
• Finding subarrays (unknown indices)

When Prefix Sum Alone is Enough

Use case: Range queries with known indices

# Query: sum from index 2 to 5
prefix = [0, 1, 3, 6, 10, 15]
sum_range = prefix[6] - prefix[2]  # No hash map needed

Example problems:

• Range Sum Query (#303)
• Matrix Range Sum (#304)

When Hash Map Alone is Enough

Use case: Finding pairs (not subarrays)

# Two Sum: Find two numbers that sum to target
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
# No prefix sum needed!

When You Need Both

Use case: Finding subarrays with target sum

def subarraySum(nums, k):
    count = 0
    prefix_sum = 0  # Prefix sum
    sum_count = {0: 1}  # Hash map
    
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
    
    return count

Why both:

• Prefix sum: Track cumulative sums
• Hash map: Find matching prefix sums quickly

Decision Framework

Question: What are you looking for?

Known indices?
  → Prefix sum only

Pairs (two elements)?
  → Hash map only

Subarrays (contiguous)?
  → Prefix sum + hash map

Conclusion

Key takeaway:

• Range queries → Prefix sum
• Pairs → Hash map
• Subarrays → Both

For more, see Prefix Sum + Hash Map and the complete guide.