Two Sum Problem Classic Hash Solution in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Sum Classic Hash Solution

What is the output of the following C# code that solves the Two Sum problem using a hash map?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int[] TwoSum(int[] nums, int target) {
        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[] { -1, -1 };
    }

    static void Main() {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = TwoSum(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

A [2, 3]

B [1, 2]

C [0, 1]

D [-1, -1]

💡 Hint

Think about which two numbers add up to the target 9 in the array.

The numbers 2 and 7 at indices 0 and 1 add up to 9. The code returns their indices as [0, 1].

🧠 Conceptual

intermediate

Understanding Hash Map Usage in Two Sum

Why does the Two Sum classic hash solution use a dictionary (hash map) to store numbers and their indices?

A To count how many times each number appears in the array.

B To quickly check if the complement of the current number exists in the array in constant time.

C To store all pairs of numbers that add up to the target.

D To sort the array before searching for pairs.

💡 Hint

Think about how to find a number's complement efficiently.

The dictionary allows checking if the complement exists in constant time, avoiding nested loops and reducing time complexity.

🔧 Debug

advanced

Identify the Error in Two Sum Implementation

What error will the following code produce when run?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int[] TwoSum(int[] nums, int target) {
        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.Add(nums[i], i);
        }
        return new int[] { -1, -1 };
    }

    static void Main() {
        int[] nums = {3, 3};
        int target = 7;
        int[] result = TwoSum(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

A System.ArgumentException: An item with the same key has already been added.

B [-1, -1]

C [0, 1]

D System.NullReferenceException

💡 Hint

Look at how the dictionary is updated inside the loop.

The code uses map.Add which throws an exception if the key already exists. Since nums has duplicate 3's, adding the second 3 causes an error.

❓ Predict Output

advanced

Output When No Two Sum Pair Exists

What is the output of this Two Sum code when no two numbers add up to the target?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int[] TwoSum(int[] nums, int target) {
        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[] { -1, -1 };
    }

    static void Main() {
        int[] nums = {1, 2, 3, 4};
        int target = 10;
        int[] result = TwoSum(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }
}

A [2, 3]

B [0, 3]

C [1, 2]

D [-1, -1]

💡 Hint

Check if any two numbers in the array add up to 10.

No two numbers in the array add up to 10, so the function returns [-1, -1].

🧠 Conceptual

expert

Time Complexity of Two Sum Classic Hash Solution

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

A O(n) because each element is processed once and hash lookups are O(1) on average.

B O(log n) because it uses a binary search on a sorted array.

C O(n^2) because it uses nested loops to check all pairs.

D O(n log n) because it sorts the array first then searches.

💡 Hint

Consider how many times the loop runs and the cost of dictionary operations.

The solution loops through the array once and uses a hash map for constant time lookups, resulting in O(n) time complexity.

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