Two Sum Problem Classic Hash Solution in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Two Sum problem classic hash solution?

Use a hash map to store numbers and their indices while checking if the complement (target - current number) exists in the map to find the pair efficiently.

beginner

Why do we use a hash map in the Two Sum problem?

A hash map allows quick lookup (average O(1) time) to check if the complement of the current number exists, making the solution efficient.

intermediate

What is the time complexity of the classic hash solution for Two Sum?

O(n), where n is the number of elements in the array, because each element is processed once and hash map lookups are O(1) on average.

beginner

In the Two Sum hash solution, what do we store as the key and value in the hash map?

Key: the number from the array; Value: the index of that number in the array.

beginner

What happens if no two numbers add up to the target in the Two Sum problem?

The function returns an empty array or indication that no valid pair exists.

What data structure is primarily used in the classic Two Sum hash solution?

A Stack

B Array

C Hash map

D Queue

The hash map is used for quick lookup of complements.

What is the average time complexity of looking up an element in a hash map?

A O(1)

B O(log n)

C O(n)

D O(n log n)

Hash maps provide average O(1) time complexity for lookups.

In the Two Sum hash solution, what do you check for each number in the array?

A If the number itself is zero

B If the number is at the last index

C If the number is the largest in the array

D If the complement (target - number) exists in the hash map

We check if the complement exists to find the pair that sums to the target.

What do you store as the value in the hash map in the Two Sum solution?

A The index of the number

B The target value

C The number itself

D The sum of all numbers

The index is stored to return the positions of the two numbers.

What should the Two Sum function return if no pair is found?

A The target value

B Null or empty array

C The entire array

D The first element

Returning null or empty array indicates no valid pair was found.

Explain how the hash map helps solve the Two Sum problem efficiently.

Think about how you find a matching number quickly without checking all pairs.

Describe the step-by-step process of the classic hash solution for Two Sum.

Imagine walking through the array and using a map to remember what you saw.

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