Two Sum Problem Classic Hash Solution in DSA C#

Mental Model

We want to find two numbers that add up to a target by remembering what numbers we have seen before.

Analogy: Imagine you are shopping and want to buy two items that together cost exactly your budget. You keep a list of prices you have seen and check if the difference to your budget is already on the list.

nums: [2] [7] [11] [15]
hash: {}
↑ current index

Dry Run Walkthrough

Input: nums: [2, 7, 11, 15], target: 9

Goal: Find two indices where the numbers add up to 9

Step 1: Check number 2 at index 0, look for 9 - 2 = 7 in hash

nums: [2] [7] [11] [15]
hash: {}
↑ i=0, num=2

Why: We want to see if the complement 7 is already seen

Step 2: 7 not found in hash, add 2 with index 0 to hash

nums: [2] [7] [11] [15]
hash: {2:0}
↑ i=1, num=7

Why: Remember 2 for future complements

Step 3: Check number 7 at index 1, look for 9 - 7 = 2 in hash

nums: [2] [7] [11] [15]
hash: {2:0}
↑ i=1, num=7

Why: Check if complement 2 is seen

Step 4: 2 found in hash at index 0, return indices [0,1]

nums: [2] [7] [11] [15]
hash: {2:0}
result: [0,1]

Why: Found two numbers that add to target

Result:

nums: [2] [7] [11] [15]
result: indices [0,1]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

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

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

for (int i = 0; i < nums.Length; i++) {

iterate over each number to check complements

int complement = target - nums[i];

calculate the needed number to reach target

if (hash.ContainsKey(complement)) {

check if complement was seen before

return new int[] { hash[complement], i };

return indices of the two numbers adding to target

hash[nums[i]] = i;

store current number and its index for future checks

Output

[0, 1]

Complexity Analysis

Time: O(n) because we scan the list once and do constant time hash lookups

Space: O(n) because we store seen numbers in a hash map

vs Alternative: Compared to checking all pairs (O(n^2)), this is much faster by using extra space

Edge Cases

empty array

returns [-1, -1] because no pairs exist

DSA C#

return new int[] { -1, -1 };

no two numbers add to target

returns [-1, -1] after full scan

DSA C#

return new int[] { -1, -1 };

two identical numbers add to target

correctly returns their indices if both appear

DSA C#

hash[nums[i]] = i;

When to Use This Pattern

When you need to find two elements summing to a target quickly, use a hash map to remember seen numbers and check complements in one pass.

Common Mistakes

Mistake: Checking for complement after adding current number to hash causes wrong results
Fix: Check for complement before adding current number to hash

Mistake: Returning indices in wrong order or returning values instead of indices
Fix: Return stored index of complement and current index as a pair

Summary

Finds two indices of numbers that add up to a target using a hash map.

Use when you want a fast solution to find pairs summing to a target in an array.

Remember to check for complement before storing current number to avoid missing pairs.

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