Subarray Sum Equals K Using Hash Map in DSA Java - Build from Scratch

Subarray Sum Equals K Using Hash Map

📖 Scenario: You are analyzing daily sales data for a small shop. You want to find how many continuous days had sales that add up exactly to a target number.

🎯 Goal: Build a Java program that counts the number of continuous subarrays whose sum equals a given target k using a hash map for efficient lookup.

📋 What You'll Learn

Create an integer array called sales with exact values: {1, 2, 3, -2, 5}

Create an integer variable called k and set it to 5

Use a HashMap<Integer, Integer> called prefixSumCount to store prefix sums and their counts

Implement a loop to iterate over sales and calculate the number of subarrays summing to k

Print the final count of such subarrays

💡 Why This Matters

🌍 Real World

Finding continuous periods of sales or data points that meet a target sum is useful in finance, marketing, and data analysis.

💼 Career

This technique is common in software engineering roles involving data processing, algorithm design, and performance optimization.

1

Create the sales data array

Create an integer array called sales with these exact values: {1, 2, 3, -2, 5}

DSA Java

// Your code here

Hint

Use int[] sales = {1, 2, 3, -2, 5}; to create the array.

2

Set the target sum k

Create an integer variable called k and set it to 5

DSA Java

int[] sales = {1, 2, 3, -2, 5};
// Your code here

Hint

Use int k = 5; to set the target sum.

3

Calculate the count of subarrays summing to k

Create a HashMap<Integer, Integer> called prefixSumCount and initialize it with 0 sum count as 1. Then, use a for loop with variable num to iterate over sales, update a variable currentSum by adding num, check if currentSum - k exists in prefixSumCount to update a variable count, and update prefixSumCount with currentSum count.

DSA Java

int[] sales = {1, 2, 3, -2, 5};
int k = 5;
// Your code here

Hint

Use a hash map to store counts of prefix sums. Update count when currentSum - k is found.

4

Print the count of subarrays

Print the variable count to display the number of continuous subarrays in sales that sum to k

DSA Java

import java.util.HashMap;

int[] sales = {1, 2, 3, -2, 5};
int k = 5;
HashMap prefixSumCount = new HashMap();
prefixSumCount.put(0, 1);
int currentSum = 0;
int count = 0;
for (int num : sales) {
    currentSum += num;
    if (prefixSumCount.containsKey(currentSum - k)) {
        count += prefixSumCount.get(currentSum - k);
    }
    prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
}
// Your code here

Hint

Use System.out.println(count); to print the result.

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)