Two Sum Problem Classic Hash Solution in DSA C# - Time & Space Complexity

Time Complexity: Two Sum Problem Classic Hash Solution

O(n)

Understanding Time Complexity

We want to understand how fast the Two Sum solution using a hash works as the input grows.

Specifically, how does the time to find two numbers that add up to a target change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int[] TwoSum(int[] nums, int target) {
    var 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 };
}
    

This code finds two numbers in the array that add up to the target using a hash map for quick lookups.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop over the array elements.
• How many times: Exactly once for each element, so n times if n is the array length.
• Inside the loop, hash map lookups and insertions happen in constant time on average.

How Execution Grows With Input

Each element is checked once, and the hash map operations are very fast, so the total work grows directly with the number of elements.

Input Size (n)	Approx. Operations
10	About 10 checks and lookups
100	About 100 checks and lookups
1000	About 1000 checks and lookups

Pattern observation: The work grows in a straight line as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two numbers grows directly in proportion to the size of the input array.

Common Mistake

[X] Wrong: "Because there is a loop inside a loop, the time is O(n²)."

[OK] Correct: There is only one loop, and the hash map lookups inside it happen very fast, not another full loop.

Interview Connect

Understanding this solution's time complexity shows you can use data structures smartly to speed up problems.

This skill is useful in many coding challenges and real projects where speed matters.

Self-Check

"What if we used a simple nested loop instead of a hash map? How would the time complexity change?"

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