LeetCode #1, Two Sum Explained: The HashMap Pattern Behind O(n) Solutions

Two Sum in C# & JavaScript: The HashMap Pattern Explained

LeetCode Problem #1 — Two Sum

The Two Sum problem is one of the most popular beginner problems on LeetCode. It looks simple at first, but it teaches one of the most important patterns in coding interviews: using a HashMap to reduce an O(n²) problem to O(n).

In this article, we will understand the problem, derive the efficient approach step by step, walk through the algorithm using an example, and implement it in both C# and JavaScript.

💡 The key idea:
Don't search for the second number. Calculate what the second number needs to be.

📌 Problem Statement

You are given an integer array nums and an integer target. Your task is to find the indices of two numbers whose sum is equal to the target.

You can assume that exactly one valid solution exists, and you cannot use the same element twice. The answer can be returned in any order.

For the official problem statement and constraints, see LeetCode — Two Sum .

Example

nums = [2, 7, 11, 15]
target = 9

We need to find two numbers whose sum is 9.

Here:

2 + 7 = 9

The indices are:

2 → index 0
7 → index 1

Therefore, the answer is:

[0, 1]

🧠 First Thought: The Brute Force Approach

The most straightforward solution is to compare every number with every other number.

For example:

for every i
    for every j
        check if nums[i] + nums[j] == target

This works, but there is a problem.

If the array contains 10,000 elements, checking every possible pair can require roughly n² comparisons.

⚠️ Problem:
Brute force has a time complexity of O(n²). The Two Sum problem specifically asks us to find an approach better than O(n²).

🚀 The Important Observation

Instead of asking:

"Which number should I pair with the current number?"

We can ask:

"What number do I need to reach the target?"

Suppose:

current number = 2
target = 9

The number we need is:

9 - 2 = 7

So instead of searching through the rest of the array for 7, we can simply check whether we have already seen 7.

🧩 The Formula

If the current number is x, we need another number y such that:

x + y = target

Rearranging the equation:

y = target - x

That gives us the key formula:

complement = target - current number

🗂️ Why Do We Need a Dictionary / HashMap?

We need a data structure that can quickly tell us whether a number has already appeared.

A HashMap is perfect for this.

In C#, we use:

Dictionary<int, int>

We store:

number → index

For example:

Number	Index
2	0
7	1

This allows us to check whether a required number exists in approximately constant time.

🔄 How the Algorithm Works

For every element in the array, we perform three simple steps.

1️⃣ Calculate the complement
complement = target - nums[i]

2️⃣ Check the Dictionary
If the complement already exists, we have found the answer.

3️⃣ Store the current number
If the complement doesn't exist, store the current number and its index.

🔍 Step-by-Step Example

Let's use:

nums = [2, 7, 11, 15]
target = 9

Step 1 — Number 2

Current number:

2

Calculate the complement:

9 - 2 = 7

Does the dictionary contain 7?

No.

So we store:

2 → 0

Step 2 — Number 7

Current number:

7

Calculate the complement:

9 - 7 = 2

Now we check the dictionary.

We already have:

2 → 0

So we found the required pair.

The current index is 1, therefore:

[0, 1]

We can immediately return the result without processing the remaining elements.

📊 Visualizing the Process

Array

[ 2, 7, 11, 15 ]

↓

Current = 2

↓

Complement = 9 - 2 = 7

↓

Is 7 already stored?

↓

❌ No

↓

Store 2 → index 0

---

Current = 7

↓

Complement = 9 - 7 = 2

↓

Is 2 already stored?

↓

✅ Yes

↓

Return [0, 1]

⚠️ Why Do We Check First and Store Later?

This is a very important detail in the implementation.

The order should be:

1. Calculate complement
2. Check dictionary
3. Store current number

Consider this example:

nums = [3, 3]
target = 6

For the first 3:

6 - 3 = 3

The dictionary doesn't contain 3, so we store the first occurrence.

For the second 3, the complement is again 3. This time, the first 3 already exists in the dictionary.

Therefore we return:

[0, 1]

✅ Important:
Checking before storing ensures that we never accidentally use the same array element twice. It also naturally handles duplicate values.

💻 C# Solution

Here is the C# implementation using Dictionary<int, int>:

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> dic = new Dictionary<int, int>();

        for(int i = 0; i < nums.Length; i++){
            int val = target - nums[i];

            if(dic.ContainsKey(val)){
                return [dic.GetValueOrDefault(val), i];
            }
            else{
                dic[nums[i]] = i;
            }
        }

        return [];
    }
}

💻 JavaScript Solution

The same HashMap approach can also be implemented in JavaScript using the built-in Map.

JavaScript solution:

var twoSum = function(nums, target) {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }

    return [];
};

⏱️ Time and Space Complexity

Approach	Time	Space
Brute Force	O(n²)	O(1)
HashMap / Dictionary	O(n) average	O(n)

Why is the optimized solution O(n)?

We iterate through the array only once. Each dictionary lookup and insertion takes O(1) average time.

Therefore:

n elements × O(1) lookup
= O(n)

🎯 The General Pattern Behind Two Sum

The most valuable part of this problem isn't just the solution. It's the pattern that you can reuse in many other problems.

Store what you've seen
↓
Calculate what you need
↓
Look it up
↓
Return the answer

Whenever you see a problem involving:

• Finding a pair
• Finding a complement
• Checking whether something appeared before
• Counting occurrences
• Finding duplicates
• Matching values efficiently

you should consider whether a HashMap / Dictionary can help.

🎤 Interview Explanation

If an interviewer asks you to explain your solution, you can describe it simply:

"I iterate through the array and calculate the complement of the current number by subtracting it from the target. I store previously seen numbers along with their indices in a HashMap. Before storing the current number, I check whether its complement already exists in the map. If it does, I return the stored index and the current index. This allows the problem to be solved in O(n) average time instead of O(n²)."

🧠 What You Should Remember

• Brute force checks every possible pair and takes O(n²).
• The target tells us exactly what number we need.
• Use target - current to calculate the complement.
• Store numbers along with their indices.
• Check the HashMap before storing the current number.
• The HashMap approach takes O(n) average time.
• The same pattern works across different programming languages.

🚀 Final Takeaway

Two Sum is often presented as a very easy problem, but the underlying idea is extremely useful. The important lesson isn't simply knowing how to solve Two Sum. It's recognizing when you can replace repeated searching with constant-time HashMap lookups.

Instead of repeatedly asking:

"Where is the number I need?"

calculate it first:

What I need = Target − What I currently have

That simple change in thinking turns the solution from a nested-loop O(n²) approach into an efficient O(n) average-time solution.

---

📌 Problem: LeetCode — Two Sum

Languages covered: C# and JavaScript