Two Sum Problem Classic Hash Solution in DSA Java - Execution Trace

Concept Flow - Two Sum Problem Classic Hash Solution

Start with empty hash map

↓

For each number in array

↓

Calculate complement = target - current number

↓

Check if complement in hash map?

Yes→Return indices

No↓

Add current number and index to hash map

↓

Repeat for next number

↓

If no pair found

→Return no solution

We scan the array once, storing numbers and their indices in a hash map. For each number, we check if its complement to reach the target is already stored. If yes, we return the pair of indices.

Execution Sample

DSA Java

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[0];
}

This code finds two indices in nums whose values add up to target using a hash map for quick lookup.

Execution Table

Step	Operation	Current Number (nums[i])	Complement (target - nums[i])	Hash Map State	Action	Result
1	Start loop i=0	2	7	{}	Check complement 7 in map? No	Add (2->0) to map
2	Next i=1	7	2	{2=0}	Check complement 2 in map? Yes	Return indices [0,1]
3	End	-	-	-	-	Solution found, loop ends

💡 At step 2, complement 2 is found in map, so indices [0,1] are returned and execution stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
i	-	0	1	1
nums[i]	-	2	7	7
complement	-	7	2	2
map	{}	{2=0}	{2=0}	{2=0}

Key Moments - 3 Insights

Why do we check if the complement is in the map before adding the current number?

Because if we add the current number first, we might find the same number as complement and return the same index twice. Checking first ensures we find a different number that was seen earlier (see execution_table step 2).

What happens if no two numbers add up to the target?

The loop finishes without returning, and the function returns an empty array as shown in the code after the loop (not reached in this example).

Why do we store number as key and index as value in the map?

Because we want to quickly check if a needed number (complement) exists and get its index to return. The map lets us find indices in O(1) time.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what is the hash map state after adding the current number?

A {2=0}

B {}

C {7=1}

D {2=1}

💡 Hint

Check the 'Hash Map State' and 'Action' columns at step 1 in execution_table.

At which step does the function find the solution and stop?

A Step 1

B Step 3

C Step 2

D No solution found

💡 Hint

Look at the 'Result' column in execution_table where indices are returned.

If the input array was [3, 3] and target 6, what would the hash map contain after the first iteration?

A {6=0}

B {3=0}

C {}

D {3=1}

💡 Hint

Refer to variable_tracker and execution_table logic for adding current number to map.

Concept Snapshot

Two Sum Classic Hash Solution:
- Use a hash map to store number -> index
- For each number, compute complement = target - number
- Check if complement in map: if yes, return indices
- Else, add current number and index to map
- Runs in O(n) time with O(n) space

Full Transcript

The Two Sum problem finds two numbers in an array that add up to a target. This classic hash solution uses a hash map to store numbers and their indices as we scan the array once. For each number, we calculate the complement needed to reach the target. We check if this complement is already in the map. If yes, we return the stored index and current index. Otherwise, we add the current number and its index to the map and continue. This approach avoids nested loops and runs efficiently in linear time. The execution table shows each step: starting with an empty map, adding the first number, then finding the complement on the second number and returning the solution. Variable tracking shows how indices, numbers, complements, and the map change step by step. Key moments clarify why we check complement before adding current number, what happens if no solution exists, and why the map stores number to index. The visual quiz tests understanding of map state and stopping condition. This method is a common and efficient way to solve Two Sum.

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