The Two Sum problem sounds complicated, but it's actually very simple.
Imagine you have a list of numbers:
int[] numbers = { 2, 7, 11, 15 };
And someone asks you:
"Can you find two numbers that add up to 9?"
Looking at the list, you can see that:
2 + 7 = 9
So the answer is the first two numbers in the array.
The Code
public static (int, int) TwoSum(int[] arr, int target)
{
var seen = new Dictionary<int, int>();
for (int i = 0; i < arr.Length; i++) {
int need = target - arr[i];
if (seen.TryGetValue(need, out int index)) {
return (index, i);
}
seen[arr[i]] = i;
}
return (-1, -1);
}
Let's Break It Down
Step 1: Create a Dictionary
var seen = new Dictionary<int, int>();
Think of a dictionary as a notebook.
Every time we see a number, we write it down together with its position in the array.
This lets us quickly check whether we've seen a number before.
Step 2: Look at Every Number
for (int i = 0; i < arr.Length; i++)
We go through the array one number at a time.
Step 3: Figure Out What's Missing
int need = target - arr[i];
Suppose our target is 9.
If the current number is 2, we ask:
"What number do I need to reach 9?"
9 - 2 = 7
So now we're looking for 7.
Step 4: Have We Already Seen It?
if (seen.TryGetValue(need, out int index))
We check our notebook.
If 7 is already there, we've found our pair!
We return both positions
Step 5: If Not, Save the Current Number
seen[arr[i]] = i;
If we didn't find the missing number, we simply remember the current number for later.
Then we move on to the next one.
Example
Array:
[2, 7, 11, 15]
Target:
9
First number: 2
Need:
9 - 2 = 7
Have we seen 7?
No.
Store:
2 → index 0
Second number: 7
Need:
9 - 7 = 2
Have we seen 2?
Yes!
We stored it earlier.
Return: (0, 1)
Done!
Why Is This Fast?
A beginner might try this:
Compare the first number with every other number.
Then compare the second number with every other number.
Then the third...
This works, but it repeats a lot of work.
Our solution is smarter.
Instead of searching over and over, we simply remember the numbers we've already seen.
It's like meeting people at a party. Instead of asking everyone their name every time, you remember the names as you meet them. The next time you see someone, you recognize them immediately.
Complexity
Time: O(n) — we only go through the array once.
Space: O(n) — we store the numbers we've seen in a dictionary.
Final Thoughts
The trick to solving the Two Sum problem isn't doing more work—it's remembering what you've already seen.
That's why a Dictionary is the perfect tool for the job. It lets us check for numbers almost instantly, making the algorithm both simple and efficient.
