Two Sum Problem Classic Hash Solution in DSA C# - 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 the complement to reach the target exists in the map. If yes, we return the pair.

Execution Sample

DSA C#

int[] nums = {2, 7, 11, 15};
int target = 9;
Dictionary<int,int> map = new Dictionary<int,int>();
for (int i = 0; i < nums.Length; i++) {
  int complement = target - nums[i];
  if (map.ContainsKey(complement)) return new int[] {map[complement], i};
  map[nums[i]] = i;
}
return new int[0];

Find two indices in nums whose values add up to target using a hash map for fast 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	i=1	7	2	{2:0}	Check complement 2 in map? Yes	Return indices [0,1]
3	Exit	-	-	-	-	Solution found, loop ends

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
i	undefined	0	1	1
nums[i]	undefined	2	7	7
complement	undefined	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 the complement is already in the map, it means we found the pair that sums to target. Adding current number first would miss this check at the same iteration. See execution_table step 2 where complement 2 is found before adding 7.

What happens if no two numbers sum to the target?

The loop finishes without returning, and the function returns no solution. The map ends up containing all numbers with their indices. This is implied after the last step in execution_table where no return occurs.

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

Because we want to quickly check if a number exists (key lookup) and retrieve its index (value) to return the answer. This is shown in variable_tracker where map stores number:index pairs.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what is the state of the hash map after processing nums[0]?

A {"2":0}

B {}

C {"7":0}

D {"2":1}

💡 Hint

Check the 'Hash Map State' column at step 1 in execution_table.

At which step does the algorithm 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 target was 18 instead of 9, what would happen at step 2?

A Complement found in map, return indices

B Complement not found, add current number to map

C Loop ends immediately

D Error occurs

💡 Hint

Think about complement calculation and map lookup at step 2 in execution_table.

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:
  - Yes: return indices
  - No: add current number to map
- Runs in O(n) time with one pass
- Returns first valid pair found

Full Transcript

This visualization shows the classic hash map solution for the Two Sum problem. We start with an empty map and scan the array. 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 indices immediately. If not, we add the current number and its index to the map and continue. The execution table traces each step, showing the map state and actions. The variable tracker shows how variables change. Key moments clarify common confusions about order of operations and map usage. The quiz tests understanding of the map state and flow. This approach finds the first pair summing to target in one pass efficiently.

Practice

1. What is the main purpose of using a hash map in the Two Sum Problem Classic Hash Solution?

easy

A. To store the sum of all pairs

B. To sort the array before searching

C. To reverse the array elements

D. To quickly check if the complement of the current number exists

Solution

1. Step 1: Understand the role of hash map

   The hash map stores numbers and their indices for quick lookup.

2. Step 2: Use hash map to find complement

   For each number, check if (target - number) exists in the map to find the pair.

3. Final Answer:

   To quickly check if the complement of the current number exists -> Option D

4. Quick Check:

   Hash map = fast complement check [OK]

Hint: Hash map helps find pairs in one pass [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Trying to store sums instead of indices
• Ignoring the complement concept

2. Which of the following is the correct syntax to declare a dictionary in C# for the Two Sum problem?

easy

A. Dictionary map = new Dictionary();

B. var map = new List<int>();

C. HashMap map = new HashMap();

D. Dictionary map = new Dictionary();

Solution

1. Step 1: Identify correct dictionary declaration

   In C#, Dictionary<int, int> is used for key-value pairs.

2. Step 2: Check syntax correctness

   Dictionary map = new Dictionary(); correctly declares and initializes the dictionary.

3. Final Answer:

   Dictionary map = new Dictionary(); -> Option A

4. Quick Check:

   C# dictionary syntax = Dictionary map = new Dictionary(); [OK]

Hint: Use Dictionary for key-value pairs [OK]

Common Mistakes:

• Using List instead of Dictionary
• Using Java's HashMap syntax in C#
• Not specifying generic types

3. What will be the output of the following C# code snippet for input array [2, 7, 11, 15] and target 9?

public int[] TwoSum(int[] nums, int target) {
    Dictionary map = new Dictionary();
    for (int i = 0; i < nums.Length; i++) {
        int complement = target - nums[i];
        if (map.ContainsKey(complement)) {
            return new int[] { map[complement], i };
        }
        map[nums[i]] = i;
    }
    return new int[] { -1, -1 };
}

medium

A. [1, 2]

B. [0, 1]

C. [-1, -1]

D. [2, 3]

Solution

1. Step 1: Trace the loop and map updates

   At i=0, map is empty; add (2,0). At i=1, complement=9-7=2 found in map at index 0.

2. Step 2: Return indices of complement and current

   Return [0,1] as the pair sums to 9.

3. Final Answer:

   [0, 1] -> Option B

4. Quick Check:

   nums[0]+nums[1] = 2+7 = 9 [OK]

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

Common Mistakes:

• Returning indices in wrong order
• Not updating map correctly
• Returning [-1, -1] incorrectly

4. Identify the bug in this Two Sum solution code snippet:

public int[] TwoSum(int[] nums, int target) {
    Dictionary map = new Dictionary();
    for (int i = 0; i <= nums.Length; i++) {
        int complement = target - nums[i];
        if (map.ContainsKey(complement)) {
            return new int[] { map[complement], i };
        }
        map[nums[i]] = i;
    }
    return new int[] { -1, -1 };
}

medium

A. Dictionary should be a List

B. Complement calculation is wrong

C. Loop condition should be < instead of <=

D. Return statement is missing

Solution

1. Step 1: Check loop boundary

   The loop uses i <= nums.Length which causes index out of range error.

2. Step 2: Correct loop condition

   Change to i < nums.Length to avoid accessing invalid index.

3. Final Answer:

   Loop condition should be < instead of <= -> Option C

4. Quick Check:

   Loop boundary off by one causes error [OK]

Hint: Use < length for array loops to avoid errors [OK]

Common Mistakes:

• Using <= instead of < in loop
• Confusing data structures
• Ignoring index out of range exceptions

5. Given the array [3, 3, 4, 5] and target 6, what will the Two Sum hash solution return and why?

hard

A. [0, 1] because the first two 3's sum to 6

B. [1, 2] because 3 and 4 sum to 6

C. [-1, -1] because no pair sums to 6

D. [2, 3] because 4 and 5 sum to 6

Solution

1. Step 1: Trace the map and complements

   At i=0, map empty, add (3,0). At i=1, complement=6-3=3 found at index 0.

2. Step 2: Return indices of matching pair

   Return [0,1] because nums[0]+nums[1]=3+3=6.

3. Final Answer:

   [0, 1] because the first two 3's sum to 6 -> Option A

4. Quick Check:

   Duplicate values handled correctly [OK]

Hint: Duplicates can form valid pairs if indices differ [OK]

Common Mistakes:

• Ignoring duplicates in map
• Assuming no pair exists with same number twice
• Returning wrong indices