Subarray Sum Equals K Using Hash Map in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Subarray Sum Count with k=5

What is the output of the following Java code that counts subarrays summing to k=5?

DSA Java

import java.util.HashMap;
public class Solution {
    public static int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap<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);
        }
        return count;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2, 1};
        System.out.println(subarraySum(nums, 5));
    }
}

A 5

B 2

C 4

D 3

💡 Hint

Count all continuous subarrays whose sum equals 5.

The subarrays that sum to 5 are [2,3] (indices 1-2), [3,2] (indices 2-3), and [2,3,2,1] (indices 1-4). The code correctly counts 3 such subarrays.

🧠 Conceptual

intermediate

Why use a HashMap in Subarray Sum Equals K?

Why do we use a HashMap to solve the Subarray Sum Equals K problem efficiently?

A To store the frequency of prefix sums for quick lookup of needed sums.

B To store all subarrays explicitly for counting sums.

C To sort the array elements for binary search of subarrays.

D To keep track of the maximum subarray sum found so far.

💡 Hint

Think about how prefix sums help find subarrays quickly.

The HashMap stores how many times each prefix sum has appeared. This helps quickly find if a subarray sum equals k by checking if (current_sum - k) exists.

🔧 Debug

advanced

Identify the error in this Subarray Sum code

What is the output of this Java code when run?

DSA Java

import java.util.HashMap;
public class Solution {
    public static int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(subarraySum(nums, 3));
    }
}

A 2

B NullPointerException

C 1

D 0

💡 Hint

Check if the map is initialized with prefix sum 0.

The map does not have an initial entry for prefix sum 0, so when sum-k equals 0 it skips counting subarrays from the start. Outputs 1 (only [3]), missing [1,2]. No exception.

❓ Predict Output

advanced

Output of Subarray Sum Count with negative numbers

What is the output of this Java code counting subarrays summing to k=0 with negative numbers?

DSA Java

import java.util.HashMap;
public class Solution {
    public static int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap<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);
        }
        return count;
    }
    public static void main(String[] args) {
        int[] nums = {1, -1, 0};
        System.out.println(subarraySum(nums, 0));
    }
}

A 0

B 3

C 1

D 2

💡 Hint

Count all subarrays that sum to zero including single elements.

The subarrays summing to 0 are [1, -1], [1, -1, 0], [0]. The code counts 3 such subarrays.

🚀 Application

expert

Maximum number of subarrays summing to k in large array

Given an array of 10^6 elements all equal to 1, and k=2, how many subarrays sum to k?

A 999999

B 1000000

C 999998

D 1000001

💡 Hint

Count how many pairs of consecutive 1s exist in the array.

Each subarray of length 2 sums to 2. There are (n-1) such subarrays in an array of length n=10^6, so 999999.

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)