Two Sum Problem Classic Hash Solution in DSA Java - Build from Scratch

Two Sum Problem Classic Hash Solution

📖 Scenario: Imagine you are helping a cashier at a store. The cashier has a list of prices for items bought by a customer. The customer wants to pay exactly a certain amount using two items from the list. Your job is to find the two items that add up to that exact amount.

🎯 Goal: Build a Java program that finds two numbers in an array that add up to a given target sum using a hash map for quick lookup.

📋 What You'll Learn

Create an integer array called nums with the values {2, 7, 11, 15}.

Create an integer variable called target and set it to 9.

Use a HashMap<Integer, Integer> called map to store numbers and their indices.

Use a for loop with variable i to iterate over nums.

Inside the loop, check if target - nums[i] exists in map.

If it exists, print the indices as an array in the format [index1, index2].

If it does not exist, add nums[i] and i to map.

💡 Why This Matters

🌍 Real World

Finding two items that sum to a specific value is useful in shopping apps, budgeting tools, and financial software to quickly find matching pairs.

💼 Career

This problem is a common coding interview question and helps develop skills in using hash maps and arrays efficiently.

1

Create the input array

Create an integer array called nums with the values {2, 7, 11, 15}.

DSA Java

// Create the integer array nums with values {2, 7, 11, 15}
// Your code here

Hint

Use int[] nums = {2, 7, 11, 15}; inside the main method.

2

Set the target sum

Create an integer variable called target and set it to 9 inside the main method after the array.

DSA Java

public class TwoSum {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        // Create the integer variable target and set it to 9
        // Your code here
    }
}

Hint

Use int target = 9; after the array declaration.

3

Implement the hash map logic to find two sum

Create a HashMap<Integer, Integer> called map. Use a for loop with variable i to iterate over nums. Inside the loop, check if target - nums[i] exists in map. If it exists, print the indices as an array in the format [index1, index2] and break the loop. If it does not exist, add nums[i] and i to map.

DSA Java

import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        // Create a HashMap called map
        // Use a for loop with variable i to iterate over nums
        // Inside the loop, check if target - nums[i] exists in map
        // If yes, print the indices as [map.get(target - nums[i]), i] and break
        // Else, add nums[i] and i to map
        // Your code here
    }
}

Hint

Use HashMap<Integer, Integer> map = new HashMap<>(); and a for loop from 0 to nums.length. Inside, check if map.containsKey(target - nums[i]). If yes, print the indices and break. Otherwise, add nums[i] and i to map.

4

Print the result

Run the program to print the indices of the two numbers in nums that add up to target. The output should be in the format [0, 1].

DSA Java

import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        HashMap map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                // Print the indices in format [index1, index2]
                // Your code here
                break;
            }
            map.put(nums[i], i);
        }
    }
}

Hint

The program should print [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

Practice

1. What is the main purpose of using a hash map in the classic Two Sum problem solution?

easy

A. To store the sum of all pairs

B. To sort the array before searching

C. To store numbers and their indices for quick lookup

D. To reverse the array elements

Solution

1. Step 1: Understand the role of hash map

   The hash map stores each number as a key and its index as the value for quick access.

2. Step 2: Explain why quick lookup is needed

   Quick lookup helps find if the complement (target - current number) exists without scanning the entire array again.

3. Final Answer:

   To store numbers and their indices for quick lookup -> Option C

4. Quick Check:

   Hash map = quick index lookup [OK]

Hint: Hash map stores values for instant complement checks [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Storing sums instead of indices
• Using hash map to reverse elements

2. Which of the following is the correct Java syntax to declare a hash map for integer keys and values used in Two Sum?

easy

A. HashMap map = new HashMap();

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

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

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

Solution

1. Step 1: Identify correct generic types for HashMap

   Java uses wrapper classes Integer, not primitive int, for generics.

2. Step 2: Check syntax correctness

   HashMap map = new HashMap<>(); correctly declares HashMap with diamond operator for instantiation.

3. Final Answer:

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

4. Quick Check:

   Use wrapper classes and diamond operator [OK]

Hint: Use Integer, not int, for HashMap generics in Java [OK]

Common Mistakes:

• Using primitive types int in generics
• Missing diamond operator <>
• Incorrect Map interface usage

3. What will be the output of the following Java code snippet for input nums = [2, 7, 11, 15], target = 9?

public int[] twoSum(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}

medium

A. [1, 2]

B. [0, 1]

C. [2, 3]

D. []

Solution

1. Step 1: Trace the loop and map updates

   i=0: map={}, complement=9-2=7, not found, map={2:0} i=1: complement=9-7=2, found in map at index 0, return [0,1]

2. Step 2: Return indices of the two numbers that sum to target

   Indices 0 and 1 correspond to numbers 2 and 7 which sum to 9.

3. Final Answer:

   [0, 1] -> Option B

4. Quick Check:

   2 + 7 = 9 [OK]

Hint: Check complement in map before adding current number [OK]

Common Mistakes:

• Returning indices in wrong order
• Not checking complement before insertion
• Returning empty array incorrectly

4. Identify the error in the following Two Sum Java method and select the fix:

public int[] twoSum(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i <= nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}

medium

A. Change loop condition to i < nums.length

B. Change map to TreeMap

C. Remove map.put line

D. Change return type to List<Integer>

Solution

1. Step 1: Identify the loop boundary error

   The loop uses i <= nums.length which causes ArrayIndexOutOfBoundsException at last iteration.

2. Step 2: Fix the loop condition

   Changing to i < nums.length prevents out-of-bound access and fixes the error.

3. Final Answer:

   Change loop condition to i < nums.length -> Option A

4. Quick Check:

   Loop index must be less than array length [OK]

Hint: Use i < length, not i <= length, for array loops [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Changing map type unnecessarily
• Removing essential map insertion

5. Given the input array nums = [3, 3, 4, 5] and target = 6, what will the classic Two Sum hash solution return? Consider the code:

public int[] twoSum(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    return new int[] {};
}

hard

A. [0, 1]

B. [1, 2]

C. [2, 3]

D. []

Solution

1. Step 1: Trace the loop and map updates with duplicates

   i=0: map={}, complement=6-3=3, not found, map={3:0} i=1: complement=6-3=3, found at index 0, return [0,1]

2. Step 2: Understand handling of duplicates

   Even with duplicates, the first pair found is indices 0 and 1, both 3s summing to 6.

3. Final Answer:

   [0, 1] -> Option A

4. Quick Check:

   3 + 3 = 6 [OK]

Hint: Duplicates allowed; first matching pair returned [OK]

Common Mistakes:

• Ignoring duplicates and returning wrong indices
• Returning empty array incorrectly
• Confusing indices with values