Subarray Sum Equals K Using Hash Map in DSA Java - Execution Trace

Concept Flow - Subarray Sum Equals K Using Hash Map

Start with sum=0, map={0:1}

↓

Iterate over array elements

↓

Add current element to sum

↓

Check if (sum-k) exists in map?

Yes No↓

Add map[sum-k

↓

Update map with current sum count

↓

Repeat for next element

↓

Return total count of subarrays

We keep a running sum and use a map to count how many times each sum appears. For each new sum, we check if sum-k was seen before to find subarrays summing to k.

Execution Sample

DSA Java

int count = 0;
int sum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
for (int num : nums) {
  sum += num;
  if (map.containsKey(sum - k)) count += map.get(sum - k);
  map.put(sum, map.getOrDefault(sum, 0) + 1);
}

This code counts subarrays whose sum equals k by tracking cumulative sums and their frequencies in a map.

Execution Table

Step	Operation	Current Element	Running Sum	Check sum-k in map	Count Updated	Map State
1	Initialize	N/A	0	N/A	0	{0=1}
2	Add element	1	1	sum-k=1-3=-2 not in map	0	{0=1, 1=1}
3	Add element	2	3	sum-k=3-3=0 in map with count=1	1	{0=1, 1=1, 3=1}
4	Add element	-1	2	sum-k=2-3=-1 not in map	1	{0=1, 1=1, 3=1, 2=1}
5	Add element	1	3	sum-k=3-3=0 in map with count=1	2	{0=1, 1=1, 3=2, 2=1}
6	Add element	2	5	sum-k=5-3=2 in map with count=1	3	{0=1, 1=1, 3=2, 2=1, 5=1}
7	Add element	-2	3	sum-k=3-3=0 in map with count=1	4	{0=1, 1=1, 3=3, 2=1, 5=1}
8	End	N/A	N/A	N/A	4	{0=1, 1=1, 3=3, 2=1, 5=1}

💡 All elements processed; total count of subarrays with sum k is 4

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
sum	0	1	3	2	3	5	3	3
count	0	0	1	1	2	3	4	4
map	{0=1}	{0=1,1=1}	{0=1,1=1,3=1}	{0=1,1=1,3=1,2=1}	{0=1,1=1,3=2,2=1}	{0=1,1=1,3=2,2=1,5=1}	{0=1,1=1,3=3,2=1,5=1}	{0=1,1=1,3=3,2=1,5=1}

Key Moments - 3 Insights

Why do we initialize the map with {0=1} before starting?

Because a subarray starting from index 0 that sums to k should be counted. The map entry {0=1} means sum 0 has occurred once before starting, allowing detection of subarrays starting at the beginning (see execution_table step 3).

Why do we check if (sum - k) exists in the map?

Because if (sum - k) was seen before, the subarray between that previous sum and current sum equals k. This is how we find subarrays summing to k without checking all subarrays (see execution_table steps 3, 5, 6, 7).

Why do we update the map with the current sum count after checking?

We update after checking to avoid counting the current element's sum before considering subarrays ending at this element. This order ensures correct counting of subarrays (see execution_table rows where map updates happen after count increments).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the running sum?

A 5

B 2

C 3

D 1

💡 Hint

Check the 'Running Sum' column at step 5 in the execution_table.

At which step does the count first increase from 0 to 1?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Count Updated' column in the execution_table to find when count changes from 0 to 1.

If the initial map did not contain {0=1}, what would happen to the count?

A Count would be lower

B Count would be higher

C Count would be the same

D Code would crash

💡 Hint

Refer to key_moments about why map starts with {0=1} and how it affects counting subarrays starting at index 0.

Concept Snapshot

Subarray Sum Equals K Using Hash Map:
- Keep running sum while iterating array
- Use map to store counts of sums seen
- For each sum, check if (sum-k) exists in map
- Add map[sum-k] to count for subarrays ending here
- Update map with current sum count
- Returns total count of subarrays summing to k

Full Transcript

This concept uses a running sum and a hash map to count subarrays that sum to a target k. We start with sum zero and map containing {0=1} to handle subarrays starting at the beginning. For each element, we add it to the running sum. We then check if (sum-k) exists in the map, meaning a previous sum that allows a subarray summing to k. If found, we add the count of that sum to our total count. We then update the map with the current sum's count. This process continues for all elements, and the final count is returned. The map tracks how many times each sum has appeared, enabling quick lookup and counting without checking all subarrays explicitly.

Practice

1. What is the main purpose of using a hash map in the Subarray Sum Equals K problem?

easy

A. To store cumulative sums and their frequencies for quick lookup

B. To sort the array elements before processing

C. To store the original array elements as keys

D. To keep track of the maximum subarray length

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding the number of continuous subarrays whose sum equals a target value k.

2. Step 2: Role of hash map in solution

   The hash map stores cumulative sums encountered so far and their counts, allowing quick checks if a subarray sum equals k by checking if (current_sum - k) exists.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option A

4. Quick Check:

   Hash map stores sums for fast subarray sum checks [OK]

Hint: Hash map tracks sums to find subarrays fast [OK]

Common Mistakes:

• Thinking hash map stores array elements as keys
• Assuming sorting is needed
• Using hash map to track max length instead of counts

2. Which of the following Java code snippets correctly initializes the hash map used to store cumulative sums and their counts?

easy

A. HashMap map = new HashMap();"

B. HashMap map = new HashMap<>();

C. HashMap map = new HashMap<>();

D. HashMap map = new HashMap<Integer>();

Solution

1. Step 1: Check Java generics syntax

   Java requires wrapper classes like Integer for generics, and diamond operator <> is used for type inference.

2. Step 2: Identify correct initialization

   HashMap map = new HashMap<>(); uses HashMap map = new HashMap<>(); which is correct and modern syntax.

3. Final Answer:

   HashMap map = new HashMap<>(); -> Option C

4. Quick Check:

   Use wrapper classes and diamond operator for HashMap [OK]

Hint: Use Integer, not int, and diamond operator <> [OK]

Common Mistakes:

• Using primitive types int in generics
• Missing diamond operator <>
• Incorrect constructor syntax

3. What is the output of the following Java code snippet?

int[] nums = {1, 2, 3};
int k = 3;
int count = 0;
HashMap map = new HashMap<>();
map.put(0, 1);
int sum = 0;
for (int num : nums) {
    sum += num;
    if (map.containsKey(sum - k)) {
        count += map.get(sum - k);
    }
    map.put(sum, map.getOrDefault(sum, 0) + 1);
}
System.out.println(count);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Calculate cumulative sums and check subarrays

   nums = [1,2,3], k=3 - sum=1, map has 0:1, sum-k=1-3=-2 not in map - sum=3, sum-k=0 in map with count 1, count=1 - sum=6, sum-k=3 in map with count 1, count=2

2. Step 2: Final count of subarrays with sum k

   Two subarrays sum to 3: [1,2] and [3].

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Two subarrays sum to k=3 [OK]

Hint: Track sums and check (sum-k) in map to count subarrays [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Forgetting to update count correctly
• Misunderstanding cumulative sum logic

4. Identify the error in the following Java code snippet for counting subarrays with sum k:

int[] nums = {1, -1, 0};
int k = 0;
int count = 0;
HashMap map = new HashMap<>();
int sum = 0;
for (int num : nums) {
    sum += num;
    if (map.containsKey(sum - k)) {
        count += map.get(sum - k);
    }
    map.put(sum, 1);
}
System.out.println(count);

medium

A. Incorrect array declaration syntax

B. Using sum - k instead of sum + k in map lookup

C. Not updating sum inside the loop

D. Missing initialization of map with (0,1)

Solution

1. Step 1: Check map initialization

   The map should start with (0,1) to count subarrays starting at index 0. This is missing here.

2. Step 2: Check map update logic

   Also, map.put(sum, 1) overwrites counts instead of incrementing. But the main error is missing initial (0,1).

3. Final Answer:

   Missing initialization of map with (0,1) -> Option D

4. Quick Check:

   Initialize map with (0,1) to count empty prefix sum [OK]

Hint: Always start map with (0,1) before loop [OK]

Common Mistakes:

• Not initializing map with (0,1)
• Overwriting counts instead of incrementing
• Confusing sum-k with sum+k

5. Given an array nums = {3, 4, 7, 2, -3, 1, 4, 2} and k = 7, how many continuous subarrays sum to k? Use the hash map approach to find the answer.

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate cumulative sums and track counts

   Initialize map with (0,1), sum=0, count=0 Iterate nums: - sum=3, sum-k=-4 not in map, map[3]=1 - sum=7, sum-k=0 in map(1), count=1, map[7]=1 - sum=14, sum-k=7 in map(1), count=2, map[14]=1 - sum=16, sum-k=9 not in map, map[16]=1 - sum=13, sum-k=6 not in map, map[13]=1 - sum=14, sum-k=7 in map(1), count=3, map[14]=2 - sum=18, sum-k=11 not in map, map[18]=1 - sum=20, sum-k=13 in map(1), count=4, map[20]=1

2. Step 2: Identify subarrays

   Four subarrays sum to 7: [3,4], [7], [7,2,-3,1], [1,4,2].

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count subarrays with sum k using cumulative sums [OK]

Hint: Count subarrays by checking (sum-k) in map during iteration [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Not updating counts correctly when sum repeats
• Forgetting to initialize map with (0,1)