💡 Intuition

Imagine you're playing a game where you need to find two numbers that add up to a target. Let's say the target is 10.

As you look at each number, you ask:

"What number do I need to reach 10?"

For example:

If the current number is 3, you need 7.
If the current number is 4, you need 6.
If the current number is 8, you need 2.

Instead of searching the whole list every time, we keep a small notebook that remembers all the numbers we've already seen.

When we need a number, we quickly check the notebook:

If the number is already there → 🎉 We found the answer.
If it's not there → ✍️ Write down the current number and continue.

This allows us to find the answer in a single pass through the array.

🧠 Let's Walk Through an Example

Array: [2, 7, 11, 15]
Target: 9

We'll keep a hash map called seen. It stores:

number → index

Initially:

seen = {}

Step 1

Current number = 2

What number do we need?

9 - 2 = 7

Is 7 already in our notebook?

No

So we remember 2:

seen = {
  2 → 0
}

Step 2

Current number = 7

What number do we need?

9 - 7 = 2

Is 2 already in our notebook?

Yes ✅

We previously saw 2 at index 0. Current index is 1.

So the answer is:

[0, 1]

We stop immediately because we found the pair that adds up to the target.

🔍 Step-by-Step Algorithm

Create an empty hash map called seen.
Loop through every number in the array.
Find the missing number needed to reach the target.
Check if that missing number exists in seen.
If it exists, return both indices.
If it doesn't exist, store the current number and its index.
Continue until a pair is found.

🎯 Why Does This Work?

Whenever we visit a number, every number before it has already been stored in the hash map.

So if the matching partner exists earlier in the array, we can find it instantly.

Instead of checking every possible pair, we only visit each number once.

📦 Data Structure Used

We use a Hash Map.

The hash map stores:

Number → Index

Example:

{
  2 → 0,
  7 → 1,
  11 → 2
}

This lets us check whether a number exists in almost constant time.

⏱️ Complexity Analysis

Time Complexity: O(n)

We visit each element only once.

If there are n numbers, we perform n checks.

Space Complexity: O(n)

In the worst case, we may store every number in the hash map.

So the extra space grows with the size of the input array.

✅ Fast because we avoid checking every pair.
✅ Uses extra memory to remember previously seen numbers.

68. Two Sum

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases