Subarray Sum Equals K Using Hash Map in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the count of subarrays to zero.

DSA Java

int count = [1];

Drag options to blanks, or click blank then click option'

Ak

B-1

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing count to 1 or negative values.

We start counting subarrays from zero because initially no subarrays are found.

2fill in blank

medium

Complete the code to update the cumulative sum with the current element.

DSA Java

sum [1]= nums[i];

Drag options to blanks, or click blank then click option'

A-

B*

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

We add the current element to the cumulative sum to track the sum of elements so far.

3fill in blank

hard

Fix the error in the code to check if (sum - k) exists in the map.

DSA Java

if (map.containsKey(sum [1] k)) {

Drag options to blanks, or click blank then click option'

A-

B/

C+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication instead of subtraction.

We check if (sum - k) exists to find if a subarray sums to k.

4fill in blank

hard

Fill both blanks to update count and map correctly.

DSA Java

count += map.getOrDefault(sum [1] k, 0);
map.put(sum, map.getOrDefault(sum, 0) [2] 1);

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in first blank or wrong operator in second blank.

We add the count of (sum - k) occurrences to count and increment the frequency of sum in the map.

5fill in blank

hard

Fill all three blanks to complete the method signature, initialize the map, and return the count.

DSA Java

public int [1](int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        count += map.getOrDefault(sum [2] k, 0);
        map.put(sum, map.getOrDefault(sum, 0) [3] 1);
    }
    return count;
}

Drag options to blanks, or click blank then click option'

AsubarraySum

B-

C+

DcountSubarrays

Attempts:

3 left

💡 Hint

Common Mistakes

Wrong method name, wrong operators in blanks 2 or 3.

The method is named subarraySum, uses subtraction to find (sum - k), and adds 1 to update the map.

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)