LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Prefix Sum/The {0: 1} Initialization: Why It's Critical for Subarray Sum

The {0: 1} Initialization: Why It's Critical for Subarray Sum

LeetCopilot Team
Dec 22, 2025
9 min read
Prefix SumHash MapCommon MistakesDebuggingInterview Prep
Missing the {0: 1} initialization is why your subarray sum solution fails test cases. Learn why this base case is critical, when to use {0: 1} vs {0: -1}, and how to never forget it again.
Complete Guide

The Complete Prefix Sum Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to prefix sum. Learn all variants (1D, 2D, hash map combinations), when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any prefix sum problem.

Read the complete guide

You're solving Subarray Sum Equals K. You write the prefix sum + hash map solution. You submit.

Wrong Answer.

The test case nums = [1, 2, 3], k = 6 should return 1 (the subarray [1,2,3]), but your code returns 0.

What went wrong? You forgot to initialize the hash map with {0: 1}. This tiny detail is the #1 reason prefix sum + hash map solutions fail.

In this guide, you'll learn why {0: 1} is critical, when to use {0: 1} vs {0: -1}, and how to remember this forever.

TL;DR

  • Always initialize: sum_count = {0: 1} for counting problems
  • Why: Handles subarrays that start from index 0
  • When to use {0: 1}: Counting subarrays
  • When to use {0: -1}: Finding indices or longest subarray
  • The rule: If you're using prefix sum + hash map, you need initialization

The Bug: Missing Subarrays from Index 0

Example Test Case That Fails

python
# WRONG CODE (missing initialization)
def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    sum_count = {}  # BUG: Missing {0: 1}
    
    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

# Test
nums = [1, 2, 3]
k = 6
result = subarraySum(nums, k)
print(result)  # Expected: 1, Got: 0 ❌

Why It Happens

The problem: The subarray [1, 2, 3] starts from index 0 and has sum 6.

Trace without initialization:

code
sum_count = {}

i=0: num=1, prefix=1
  Check: (1 - 6) = -5 in map? No
  sum_count = {1: 1}

i=1: num=2, prefix=3
  Check: (3 - 6) = -3 in map? No
  sum_count = {1: 1, 3: 1}

i=2: num=3, prefix=6
  Check: (6 - 6) = 0 in map? No ❌
  sum_count = {1: 1, 3: 1, 6: 1}

count = 0 (WRONG!)

The issue: When prefix_sum = 6, we check if 0 exists in the map. But we never added 0 because we didn't initialize!

Trace with initialization:

code
sum_count = {0: 1}  ✓

i=0: num=1, prefix=1
  Check: (1 - 6) = -5 in map? No
  sum_count = {0: 1, 1: 1}

i=1: num=2, prefix=3
  Check: (3 - 6) = -3 in map? No
  sum_count = {0: 1, 1: 1, 3: 1}

i=2: num=3, prefix=6
  Check: (6 - 6) = 0 in map? Yes! ✓
  count += sum_count[0] = 1
  sum_count = {0: 1, 1: 1, 3: 1, 6: 1}

count = 1 (CORRECT!)

Why We Need {0: 1}

The Base Case

The initialization {0: 1} represents the base case: a prefix sum of 0 before we process any elements.

Conceptually:

code
Before processing any elements:
  prefix_sum = 0
  We've seen this prefix sum once
  So: sum_count = {0: 1}

This allows us to detect subarrays that start from index 0.

Visual Example

code
nums = [3, 4, 7, 2], k = 7

Subarrays with sum 7:
1. [3, 4] from index 0 to 1
2. [7] from index 2 to 2

Without {0: 1}:
  When we reach index 2, prefix_sum = 14
  We check if (14 - 7) = 7 exists
  But we haven't seen prefix_sum = 7 yet!
  We miss the subarray [7]

With {0: 1}:
  When we reach index 2, prefix_sum = 14
  We check if (14 - 7) = 7 exists
  We have seen it at index 1!
  We find the subarray [7] ✓
  
Wait, let me recalculate...

Actually for [3, 4, 7, 2], k = 7:
prefix sums: 0, 3, 7, 14, 16

When prefix = 7 (after processing [3,4]):
  Check: (7 - 7) = 0 in map? Yes! (from initialization)
  Found subarray [3, 4] ✓

When prefix = 14 (after processing [3,4,7]):
  Check: (14 - 7) = 7 in map? Yes! (from previous step)
  Found subarray [7] ✓

Code Comparison

Without initialization (buggy):

python
sum_count = {}
# Misses subarrays from index 0

With initialization (correct):

python
sum_count = {0: 1}
# Handles all subarrays correctly

When to Use {0: 1} vs {0: -1}

The initialization value depends on what you're storing in the hash map.

Use {0: 1} - Counting Subarrays

When: Counting how many subarrays meet a condition

Why: We're storing frequency (how many times we've seen each prefix sum)

Example problems:

  • Subarray Sum Equals K (#560)
  • Subarray Sums Divisible by K (#974)
  • Count Number of Nice Subarrays (#1248)
python
def subarraySum(nums, k):
    count = 0
    prefix_sum = 0
    sum_count = {0: 1}  # Frequency: seen prefix_sum=0 once
    
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in sum_count:
            count += sum_count[prefix_sum - k]  # Add frequency
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
    
    return count

Use {0: -1} - Finding Indices

When: Finding the longest subarray or returning indices

Why: We're storing earliest index for each prefix sum

Example problems:

  • Continuous Subarray Sum (#523)
  • Maximum Size Subarray Sum Equals k (#325)
  • Contiguous Array (#525)
python
def findMaxLength(nums):
    max_len = 0
    prefix_sum = 0
    sum_index = {0: -1}  # Index: prefix_sum=0 at index -1 (before start)
    
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        
        if prefix_sum in sum_index:
            max_len = max(max_len, i - sum_index[prefix_sum])
        else:
            sum_index[prefix_sum] = i  # Store earliest index
    
    return max_len

Why -1? It represents "before the array starts." If we find the same prefix sum at index i, the subarray from index 0 to i has length i - (-1) = i + 1.

Quick Decision Table

Problem TypeHash Map StoresInitialize WithExample
Count subarraysFrequency{0: 1}Subarray Sum Equals K
Find longestEarliest index{0: -1}Contiguous Array
Find any indicesEarliest index{0: -1}Continuous Subarray Sum
Check existenceBoolean/index{0: -1} or {0: True}Continuous Subarray Sum

Common Mistakes

Mistake 1: Forgetting to Initialize

❌ Wrong:

python
sum_count = {}  # Missing base case

Impact: Misses all subarrays starting from index 0

✅ Correct:

python
sum_count = {0: 1}  # For counting
# or
sum_index = {0: -1}  # For finding indices

Mistake 2: Using Wrong Initial Value

❌ Wrong:

python
# Counting problem but using index
sum_count = {0: 0}  # Should be {0: 1}

❌ Wrong:

python
# Finding longest but using frequency
sum_index = {0: 1}  # Should be {0: -1}

✅ Correct:

python
# Counting: frequency = 1
sum_count = {0: 1}

# Finding: index = -1 (before start)
sum_index = {0: -1}

Mistake 3: Initializing After the Loop

❌ Wrong:

python
sum_count = {}
for num in nums:
    prefix_sum += num
    # ... process ...
sum_count[0] = 1  # Too late!

✅ Correct:

python
sum_count = {0: 1}  # Before the loop
for num in nums:
    prefix_sum += num
    # ... process ...

Mistake 4: Initializing with Wrong Type

❌ Wrong:

python
# Counting problem but storing index
sum_count = {0: -1}  # Should be {0: 1}

Impact: When you do count += sum_count[prefix_sum - k], you'll add -1 instead of 1!

The Correct Templates

Template 1: Counting Subarrays

python
def count_subarrays(nums, k):
    """Count subarrays with sum equal to k."""
    count = 0
    prefix_sum = 0
    sum_count = {0: 1}  # Critical: frequency = 1
    
    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

Template 2: Finding Longest Subarray

python
def find_longest_subarray(nums, k):
    """Find longest subarray with sum equal to k."""
    max_len = 0
    prefix_sum = 0
    sum_index = {0: -1}  # Critical: index = -1
    
    for i, num in enumerate(nums):
        prefix_sum += num
        
        if prefix_sum - k in sum_index:
            max_len = max(max_len, i - sum_index[prefix_sum - k])
        
        # Only store if not seen before (keep earliest)
        if prefix_sum not in sum_index:
            sum_index[prefix_sum] = i
    
    return max_len

Template 3: Check Existence

python
def has_subarray_sum(nums, k):
    """Check if any subarray has sum equal to k."""
    prefix_sum = 0
    seen = {0}  # Set: just track existence
    
    for num in nums:
        prefix_sum += num
        if prefix_sum - k in seen:
            return True
        seen.add(prefix_sum)
    
    return False

Visual Walkthrough

Example: Counting Subarrays

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

Initial: sum_count = {0: 1}, prefix_sum = 0, count = 0

i=0: num=1
  prefix_sum = 1
  Check: (1 - 2) = -1 in {0: 1}? No
  sum_count = {0: 1, 1: 1}
  count = 0

i=1: num=1
  prefix_sum = 2
  Check: (2 - 2) = 0 in {0: 1, 1: 1}? Yes! ✓
  count += sum_count[0] = 1
  Found subarray [1, 1] from index 0 to 1
  sum_count = {0: 1, 1: 1, 2: 1}
  count = 1

i=2: num=1
  prefix_sum = 3
  Check: (3 - 2) = 1 in {0: 1, 1: 1, 2: 1}? Yes! ✓
  count += sum_count[1] = 1
  Found subarray [1, 1] from index 1 to 2
  sum_count = {0: 1, 1: 1, 2: 1, 3: 1}
  count = 2

Result: 2 subarrays ✓

Without {0: 1}: Would only find 1 subarray (missing the first one)

Example: Finding Longest

code
nums = [0, 1], k = 0 (treat 0 as -1, find equal 0s and 1s)

Transform: [-1, 1]

Initial: sum_index = {0: -1}, prefix_sum = 0, max_len = 0

i=0: num=-1
  prefix_sum = -1
  Check: (-1 - 0) = -1 in {0: -1}? No
  sum_index = {0: -1, -1: 0}
  max_len = 0

i=1: num=1
  prefix_sum = 0
  Check: (0 - 0) = 0 in {0: -1, -1: 0}? Yes! ✓
  max_len = max(0, 1 - (-1)) = max(0, 2) = 2
  Found subarray from index 0 to 1 with length 2
  sum_index = {0: -1, -1: 0}  # Don't update, keep earliest

Result: 2 (entire array) ✓

Without {0: -1}: Would return 0 (missing the entire array)

Testing Your Implementation

Test Cases to Verify

python
# Test 1: Subarray from start
assert subarraySum([1, 2, 3], 6) == 1  # [1,2,3]

# Test 2: Multiple subarrays
assert subarraySum([1, 1, 1], 2) == 2  # [1,1] twice

# Test 3: Entire array
assert subarraySum([3, 4, 7], 7) == 1  # [7]

# Test 4: No subarrays
assert subarraySum([1, 2, 3], 10) == 0

# Test 5: Negative numbers
assert subarraySum([1, -1, 0], 0) == 3  # [1,-1], [0], [1,-1,0]

# Test 6: Target = 0
assert subarraySum([0, 0, 0], 0) == 6  # All subarrays

Debugging Checklist

If your solution fails:

  1. Check initialization: Did you add {0: 1} or {0: -1}?
  2. Check value type: Frequency (1) or index (-1)?
  3. Check timing: Initialized before the loop?
  4. Trace manually: Print hash map state at each step
  5. Test edge case: Array that sums to k entirely

Practice Problems

Master hash map initialization with these problems:

Beginner:

  1. Subarray Sum Equals K (#560) - Use {0: 1}
  2. Running Sum of 1d Array (#1480) - No hash map needed

Intermediate:
3. Continuous Subarray Sum (#523) - Use {0: -1}
4. Contiguous Array (#525) - Use {0: -1}
5. Maximum Size Subarray Sum Equals k (#325) - Use {0: -1}

Advanced:
6. Subarray Sums Divisible by K (#974) - Use {0: 1}
7. Count Number of Nice Subarrays (#1248) - Use {0: 1}

FAQ

Q: Why {0: 1} and not {0: 0}?

A: We're counting frequency. We've seen prefix_sum = 0 once (before processing any elements), so the frequency is 1.

Q: Why {0: -1} for finding indices?

A: Index -1 represents "before the array starts." This allows subarrays starting from index 0 to have correct length calculation: i - (-1) = i + 1.

Q: What if I'm using a set instead of a map?

A: For existence checks, initialize with seen = {0}:

python
seen = {0}
for num in nums:
    prefix_sum += num
    if prefix_sum - k in seen:
        return True
    seen.add(prefix_sum)

Q: Can I skip initialization if k = 0?

A: No! Even for k = 0, you need initialization. Example: nums = [0], k = 0 should return 1, but without initialization it returns 0.

Q: What if I forget initialization in an interview?

A: Your solution will fail test cases with subarrays starting from index 0. The interviewer might give you a hint, but it's better to remember!

How to Remember Forever

Mnemonic: "Before I start, I've seen zero sum once."

Mental model: The hash map represents "what I've seen so far." Before processing any elements, I've seen a prefix sum of 0 exactly once.

Code pattern: Whenever you write:

python
prefix_sum = 0
sum_count = ???

Immediately think: "I need to initialize the base case!"

Conclusion

The {0: 1} or {0: -1} initialization is not optional—it's critical for correctness.

Key takeaways:

  • Always initialize the hash map with the base case
  • {0: 1} for counting (frequency)
  • {0: -1} for finding indices (earliest position)
  • Before the loop, not after
  • Represents the state before processing any elements

The templates:

Counting:

python
sum_count = {0: 1}

Finding longest:

python
sum_index = {0: -1}

Master this detail, and you'll never fail a subarray sum problem due to missing initialization. For more on this pattern, see Prefix Sum + Hash Map and Subarray Sum Debugging.

Next time you write prefix sum + hash map, remember: {0: 1} for counting, {0: -1} for indices.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials