Two Sum Problem Classic Hash Solution in DSA C# - Build from Scratch

Two Sum Problem Classic Hash Solution

📖 Scenario: You are working on a shopping app. You have a list of item prices, and you want to find two items that together cost exactly a gift card amount.

🎯 Goal: Build a program that finds two item indices whose prices add up to the gift card amount using a hash-based approach.

📋 What You'll Learn

Create an integer array called prices with the exact values: 2, 7, 11, 15

Create an integer variable called giftCardAmount and set it to 9

Use a Dictionary<int, int> called priceIndices to store prices and their indices

Use a for loop with variable i to iterate over prices

Inside the loop, calculate complement as giftCardAmount - prices[i]

Check if complement exists in priceIndices

If found, create an integer array result with the two indices and break the loop

Print the result array elements separated by a space

💡 Why This Matters

🌍 Real World

Finding two items that sum to a target is common in shopping apps, budgeting tools, and financial software.

💼 Career

This problem teaches hash-based lookup, a key skill for efficient data retrieval in software development.

1

Create the prices array

Create an integer array called prices with these exact values: 2, 7, 11, 15

DSA C#

# Create the prices array
// Your code here

Hint

Use int[] prices = {2, 7, 11, 15}; to create the array.

2

Set the gift card amount

Create an integer variable called giftCardAmount and set it to 9

DSA C#

int[] prices = {2, 7, 11, 15};
// Create giftCardAmount variable
// Your code here

Hint

Use int giftCardAmount = 9; to set the amount.

3

Find two indices using a dictionary

Create a Dictionary<int, int> called priceIndices. Use a for loop with variable i to iterate over prices. Inside the loop, calculate complement as giftCardAmount - prices[i]. Check if complement exists in priceIndices. If found, create an integer array result with the two indices and break the loop. Otherwise, add prices[i] and i to priceIndices.

DSA C#

int[] prices = {2, 7, 11, 15};
int giftCardAmount = 9;
// Your code here

Hint

Use a dictionary to store prices and indices. Check for complement inside the loop.

4

Print the result indices

Print the two indices stored in the result array separated by a space using Console.WriteLine.

DSA C#

int[] prices = {2, 7, 11, 15};
int giftCardAmount = 9;

var priceIndices = new Dictionary();
int[] result = new int[2];

for (int i = 0; i < prices.Length; i++)
{
    int complement = giftCardAmount - prices[i];
    if (priceIndices.ContainsKey(complement))
    {
        result[0] = priceIndices[complement];
        result[1] = i;
        break;
    }
    priceIndices[prices[i]] = i;
}
// Print the result indices
// Your code here

Hint

Use Console.WriteLine(result[0] + " " + result[1]); to print the indices.

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