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

Recall & Review

beginner

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

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

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 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.

beginner

In the Two Sum hash solution, what happens if the complement is not found in the hash map?

The current number and its index are added to the hash map for future complement checks.

beginner

Show the C# code snippet to add a number and its index to the hash map in the Two Sum solution.

hashMap[nums[i]] = i; // Adds current number as key and its index as value

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

A Array

B Stack

C Hash map (dictionary)

D Queue

The hash map allows quick lookup of complements to find the two numbers efficiently.

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

A O(n^2)

B O(n log n)

C O(log n)

D O(n)

Each element is processed once, and hash map lookups are O(1) on average, so total is O(n).

In the Two Sum problem, what do you check for each number while iterating?

A If the number itself is zero

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

C If the number is the largest in the array

D If the number is at the first index

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

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

A Numbers as keys and their indices as values

B Only the indices

C Only the numbers

D Indices as keys and numbers as values

Storing numbers as keys and indices as values allows quick complement lookup and retrieval of indices.

What happens if no two numbers sum to the target in the classic Two Sum hash solution?

A Return an empty array or null

B Return the first two indices

C Throw an error

D Return the entire array

If no pair is found, the function returns an empty array or null to indicate no solution.

Explain step-by-step how the classic hash solution finds two numbers that add up to the target.

Think about how the hash map helps find the pair quickly.

Describe why using a hash map improves the Two Sum solution compared to a brute force approach.

Focus on how lookup speed changes the algorithm.

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