Two Sum Problem Classic Hash Solution in DSA Java

Mental Model

We want to find two numbers that add up to a target by remembering numbers we've seen before.

Analogy: Imagine shopping with a list and a wallet. You check each item price and see if you have enough money left to buy another item to reach your budget exactly.

nums: [2] [7] [11] [15]
hash: {}
            ↑

Dry Run Walkthrough

Input: nums: [2, 7, 11, 15], target: 9

Goal: Find two indices where the numbers add up to 9

Step 1: Check number 2, look for 9 - 2 = 7 in hash (not found), add 2 with index 0 to hash

nums: [2↑] [7] [11] [15]
hash: {2:0}

Why: We store 2 to check if future numbers can pair with it

Step 2: Check number 7, look for 9 - 7 = 2 in hash (found at index 0), return indices [0,1]

nums: [2] [7↑] [11] [15]
hash: {2:0}

Why: Found a pair that sums to target, so we stop

Result:

Indices: [0, 1]

Annotated Code

DSA Java

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> 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[] {-1, -1}; // no solution found
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
    }
}

int complement = target - nums[i];

Calculate the number needed to reach target with current number

if (map.containsKey(complement)) {

Check if needed number was seen before

return new int[] {map.get(complement), i};

Return indices of the two numbers that sum to target

map.put(nums[i], i);

Store current number and its index for future checks

Output

Indices: [0, 1]

Complexity Analysis

Time: O(n) because we scan the list once and do constant time lookups in the hash map

Space: O(n) because we store up to n numbers in the hash map

vs Alternative: Compared to checking all pairs (O(n^2)), this hash solution is much faster by remembering seen numbers

Edge Cases

Empty array

Returns [-1, -1] since no pairs exist

DSA Java

return new int[] {-1, -1}; // no solution found

No two numbers sum to target

Returns [-1, -1] indicating no solution

DSA Java

return new int[] {-1, -1}; // no solution found

Two identical numbers sum to target

Works correctly if both numbers appear and indices differ

DSA Java

map.put(nums[i], i);

When to Use This Pattern

When asked to find two elements summing to a target quickly, use a hash map to remember seen numbers for instant lookup.

Common Mistakes

Mistake: Checking for complement after adding current number to hash map causes missing pairs
Fix: Check for complement before adding current number to hash map

Mistake: Returning indices in wrong order or returning values instead of indices
Fix: Return indices as per problem requirement, not values

Summary

Find two indices of numbers that add up to a target using a hash map.

Use when you need a fast solution to find pairs summing to a target in an array.

Remember to check for the needed complement before storing the current number.

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