Subarray Sum Equals K Using Hash Map in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using a hash map to solve the Subarray Sum Equals K problem?

We use a hash map to store the cumulative sums and their frequencies. This helps us quickly find if there is a previous cumulative sum that, when subtracted from the current cumulative sum, equals k.

beginner

In the Subarray Sum Equals K problem, what does the key in the hash map represent?

The key represents a cumulative sum of elements from the start of the array up to a certain index.

intermediate

Why do we initialize the hash map with (0, 1) before iterating the array?

Because a cumulative sum of zero occurs once before starting, which helps count subarrays that start from index 0 and sum to k.

intermediate

What is the time complexity of the Subarray Sum Equals K solution using a hash map?

The time complexity is O(n), where n is the length of the array, because we traverse the array once and perform constant-time hash map operations.

advanced

How does the hash map help in counting multiple subarrays that sum to k?

The hash map stores frequencies of cumulative sums. When the difference (current_sum - k) appears multiple times, it means multiple subarrays ending at the current index sum to k.

What does the cumulative sum represent in the Subarray Sum Equals K problem?

A Sum of elements from start up to current index

B Sum of all elements in the array

C Sum of elements from current index to end

D Sum of elements equal to k

Cumulative sum is the sum of elements from the start of the array up to the current index.

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

A To find if k is in the array

B To find if a subarray sums to zero

C To find if a previous cumulative sum allows a subarray summing to k

D To find the maximum subarray sum

If (current_sum - k) exists, it means a subarray ending at current index sums to k.

What initial value do we put in the hash map before starting the iteration?

A (0, 1)

B (k, 1)

C (1, 0)

D (0, 0)

We initialize with (0, 1) to count subarrays starting at index 0 that sum to k.

What is the space complexity of the hash map approach?

A O(1)

B O(n)

C O(k)

D O(n^2)

The hash map can store up to n cumulative sums, so space complexity is O(n).

If the array is [1, 2, 3] and k=3, how many subarrays sum to k?

A 0

B 1

C 3

D 2

Subarrays [3] and [1, 2] both sum to 3.

Explain how the hash map is used to find the number of subarrays that sum to k.

Think about how previous sums help identify subarrays ending at current index.

Describe why initializing the hash map with (0, 1) is important in this problem.

Consider what happens if the subarray starts from the very beginning.

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)