Two Sum Problem Classic Hash Solution in DSA C# - Deep Dive

Overview - Two Sum Problem Classic Hash Solution

What is it?

The Two Sum problem asks us to find two numbers in a list that add up to a specific target number. The classic hash solution uses a dictionary (hash map) to remember numbers we've seen so far and quickly check if the needed partner number exists. This approach helps us find the answer efficiently without checking every pair. It's a common problem that teaches how to use hash maps for fast lookups.

Why it matters

Without this solution, finding two numbers that add up to a target would require checking every possible pair, which is slow for large lists. The hash solution makes this process much faster, saving time and computing power. This is important in real-world apps like payment systems, games, or data analysis where quick answers matter.

Where it fits

Before learning this, you should understand arrays (lists) and basic loops. After this, you can learn about more complex hash-based problems, like three sum or using hash maps for counting and grouping.

Mental Model

Core Idea

Use a dictionary to remember numbers seen so far so you can instantly find if the matching number to reach the target exists.

Think of it like...

Imagine you are shopping with a list and a friend. You remember the prices of items you've seen, so when you find a new item, you quickly check if your friend has an item that together matches your budget.

Input array: [2, 7, 11, 15]
Target: 9

Step-by-step:

Index 0: number=2, need=7, dictionary={}
Add 2 to dictionary: {2:0}

Index 1: number=7, need=2
Check dictionary: 2 found at index 0
Return [0,1]

Result: Indices 0 and 1 sum to 9

Build-Up - 6 Steps

1

Foundation

Understanding the Two Sum Problem

Concept: Learn what the problem asks: find two numbers in a list that add up to a target.

Given an array of integers and a target number, find indices of two numbers such that they add up to the target. For example, in [2, 7, 11, 15] with target 9, 2 and 7 add up to 9, so return their indices [0,1].

Result

Clear understanding of the problem and expected output format.

Knowing exactly what the problem asks prevents confusion and guides the solution approach.

2

Foundation

Brute Force Approach Basics

Concept: Try every pair of numbers to check if they sum to the target.

Use two loops: outer loop picks one number, inner loop checks all others. If sum equals target, return indices. Example: for i in 0 to n-1: for j in i+1 to n-1: if nums[i] + nums[j] == target: return [i, j]

Result

Correct answer but slow for large lists (O(n²) time).

Trying all pairs works but is inefficient; this motivates a faster method.

3

Intermediate

Using a Dictionary for Fast Lookup

Concept: Store numbers and their indices in a dictionary to find complements quickly.

As you go through the list, calculate the number needed to reach the target (complement). Check if this complement is already in the dictionary. If yes, return indices. If no, add the current number and its index to the dictionary. Example in C#: var dict = new Dictionary(); for (int i = 0; i < nums.Length; i++) { int complement = target - nums[i]; if (dict.ContainsKey(complement)) { return new int[] { dict[complement], i }; } dict[nums[i]] = i; }

Result

Finds the two indices in one pass with O(n) time complexity.

Using a dictionary turns the problem from slow pair checking to fast lookups.

4

Intermediate

Handling Duplicate Numbers Correctly

🤔Before reading on: Do you think storing the latest index of a number in the dictionary always works correctly? Commit to yes or no.

Concept: Understand how to handle cases where the same number appears multiple times.

If the same number appears twice and can form the target (e.g., target=4, numbers=[2,2]), the dictionary must store the first occurrence before checking the second. This ensures the pair is found correctly. In the code, add the number to the dictionary only after checking for complement to avoid missing pairs with duplicates.

Result

Correctly finds pairs even when duplicates exist.

Order of operations in dictionary updates is crucial to handle duplicates without errors.

5

Advanced

Complete C# Implementation with Comments

🤔Before reading on: Do you think the dictionary lookup and insertion happen in constant time? Commit to yes or no.

Concept: See the full, runnable C# code with explanations for each step.

public int[] TwoSum(int[] nums, int target) { var dict = new Dictionary(); for (int i = 0; i < nums.Length; i++) { int complement = target - nums[i]; if (dict.ContainsKey(complement)) { return new int[] { dict[complement], i }; } dict[nums[i]] = i; // Store index of current number } throw new ArgumentException("No two sum solution"); } // Example run: // nums = [2,7,11,15], target = 9 // i=0: complement=7, dict={}, add 2:0 // i=1: complement=2, dict has 2 at 0, return [0,1]

Result

Output: [0,1] for input [2,7,11,15] and target 9.

Knowing dictionary operations are O(1) explains why this solution is efficient.

6

Expert

Why Hash Map Beats Sorting Approaches

🤔Before reading on: Is sorting the array always better for Two Sum? Commit to yes or no.

Concept: Understand why using a hash map is faster and preserves original indices compared to sorting.

Sorting the array and using two pointers can find pairs but loses original indices, which the problem requires. Also, sorting takes O(n log n) time, slower than the O(n) hash map approach. The hash map solution keeps track of original positions and is faster for large inputs.

Result

Hash map approach is optimal for Two Sum with index return requirement.

Knowing the problem constraints guides choosing the best algorithm, not just any fast method.

Under the Hood

The dictionary (hash map) stores keys as numbers from the array and values as their indices. When checking a new number, the algorithm calculates the complement needed to reach the target and queries the dictionary in constant time. If found, it returns the stored index and current index. This avoids nested loops by trading space for time.

Why designed this way?

The hash map approach was designed to reduce time complexity from quadratic to linear by using extra memory. Alternatives like sorting lose index information or are slower. Hash maps provide average O(1) lookup, making them ideal for this problem.

┌─────────────┐
│ Start array │
│ [2,7,11,15] │
└─────┬───────┘
      │
      ▼
┌─────────────────────────────┐
│ Loop through each number i   │
│ Calculate complement = target - nums[i] │
│ Check if complement in dict │
│   ┌─────────────┐           │
│   │ Found?      │──Yes─────▶│ Return indices [dict[complement], i] │
│   │ No?        │           │
│   └────┬────────┘           │
│        │                   │
│        ▼                   │
│ Add nums[i] and i to dict  │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the dictionary store all pairs of numbers and their sums? Commit yes or no.

Common Belief: The dictionary stores all pairs of numbers and their sums to find the answer.

Reality: The dictionary only stores single numbers as keys and their indices as values, not pairs or sums.

Why it matters: Thinking the dictionary stores pairs wastes memory and confuses the approach, leading to inefficient or incorrect code.

Quick: Can the Two Sum problem be solved in less than O(n) time? Commit yes or no.

Common Belief: Two Sum can be solved faster than O(n) time using clever tricks.

Reality: Because every number must be checked at least once, O(n) is the best possible time complexity for this problem.

Why it matters: Expecting faster than O(n) leads to wasted effort and misunderstanding of algorithm limits.

Quick: Does sorting the array always help solve Two Sum? Commit yes or no.

Common Belief: Sorting the array is always the best way to solve Two Sum.

Reality: Sorting loses original indices, which the problem requires to return, making it unsuitable unless extra steps are taken.

Why it matters: Using sorting without preserving indices causes wrong answers or extra complexity.

Expert Zone

1

The dictionary update happens after checking for complement to handle duplicates correctly.

2

Hash map lookups are average O(1) but can degrade to O(n) in worst cases due to collisions; understanding this helps in performance tuning.

3

Throwing an exception when no solution exists is a design choice; some implementations return null or empty arrays instead.

When NOT to use

If the input array is sorted and you only need to know if a pair exists (not indices), two-pointer technique is simpler and uses less memory. For very large data where memory is limited, hash maps may be costly.

Production Patterns

In real systems, this pattern is used in fraud detection (finding transactions summing to suspicious amounts), gaming (matching scores), and caching results for repeated queries to speed up lookups.

Connections

Hash Map Data Structure

Builds-on

Understanding hash maps deeply helps grasp why Two Sum is efficient and how to apply similar patterns to other problems.

Sliding Window Technique

Contrasts with

Sliding window solves problems with continuous subarrays, while Two Sum uses hash maps for any pair; knowing both expands problem-solving tools.

Inventory Management in Retail

Analogous pattern

Tracking items and quickly finding matching pairs in inventory is similar to Two Sum's lookup, showing how algorithms mirror real-world logistics.

Common Pitfalls

#1 Adding the current number to the dictionary before checking for complement.

Wrong approach:

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

Correct approach:

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

Root cause:

Checking after adding causes the current number to match itself, leading to incorrect pairs or missing duplicates.

#2 Returning indices of numbers after sorting the array without tracking original positions.

Wrong approach:

Array.Sort(nums);
// Use two pointers to find sum
// Return indices from sorted array directly

Correct approach:

// Use a dictionary to store original indices before sorting
// Or avoid sorting and use hash map approach

Root cause:

Sorting changes order and loses original indices, which the problem requires to return.

Key Takeaways

Two Sum asks for two numbers in a list that add up to a target and their indices.

Using a dictionary to store numbers and their indices allows fast lookup of complements in one pass.

Order of checking complement before adding current number handles duplicates correctly.

Hash map approach runs in linear time and preserves original indices, unlike sorting.

Understanding hash maps and their operations is key to mastering Two Sum and similar problems.

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