🧠 Two Sum: The Cleanest Introduction to Hash Map Thinking

Most beginners solve Two Sum with nested loops.
But the real lesson of this problem isn’t the solution—
it’s learning how to think in O(1).
Once you understand why Two Sum works, you unlock a powerful pattern used across arrays, strings, sets, and sliding windows.

🎯 Problem Summary
Given an array nums and an integer target,
return the indices of the two numbers that add up to target.

Example:

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

Output:

[0, 1]

Because:

2 + 7 = 9

🐌 The Naive O(n²) Approach

The straightforward solution checks every pair:

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i, j]

❌ Problem

• Checks all combinations
• Time complexity: O(n²)

👉 Works, but not scalable—and not interview-level.

⚡ The Key Insight

Instead of checking all pairs, flip the problem:

For each number x, ask:

👉 “What number do I need to reach the target?”

need = target - x

Now the real question becomes:

👉 “Have I seen need before?”

💡 The Pattern (Important)

Whenever you see:

“Have I seen this before?”
👉 Think:
✅ Hash map

This is one of the most important patterns in problem solving.

🏨 Hashing, Explained Intuitively

A simple real-world analogy
Imagine a hotel:

• You give your name at the front desk
• The system instantly gives your room number
• You go straight to your room

Mapping to code

Real World	Programming
Name	Key
Room number	Location
Your belongings	Value

👉 Key → location → value

Why is it fast?

Without hashing:

• You check every room ❌

With hashing:

• You go directly to the correct room ✅

🔍 Why lookup is O(1)

A Python dictionary:

• Turns a key into a specific location in memory
• Jumps directly to that location

So instead of searching:
❌ scan everything
✅ go straight to the value

👉 Key → location → value

Because lookup is O(1), we only need one pass through the array → O(n) total.

🧩 O(n) Hash Map Solution (Python)

def twoSum(nums, target):
    seen = {}  # value → index

    for i, num in enumerate(nums):
        need = target - num

        if need in seen:
            return [seen[need], i]

        seen[num] = i

This is the canonical interview solution

🔍 Step‑by‑Step Example

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

i	num	need	seen	Action
0	2	7	{}	store 2 → index 0
1	7	2	{2: 0}	2 is in seen → return [0, 1]

Done in two steps.

🧠 Why This Works

• One pass through the array → O(n)
• Each lookup is O(1)
• No nested loops

👉 Clean, fast, and interview-ready

🔁 This Isn’t Just Two Sum

This pattern shows up everywhere:

✅ Precompute → Check in O(1)

Examples:

• Subarray sum problems
• String matching
• Frequency counting
• Sliding window

👉 Once you see it, you’ll see it everywhere.

🧪 Common Variations

These frequently appear in interviews:

1. Return values instead of indices

Same idea, different output.

2. Return all pairs

Store multiple indices per value.

3. Sorted array

👉 Use two pointers, no hash map needed.

4. Two Sum in a BST

👉 Traverse + use a set.

5. Duplicates

👉 Still works—just manage indices carefully.

📝 Key Takeaways

• Two Sum is the foundation of hash map thinking
• The real trick is:

👉 “What do I need?”

• Hash maps turn O(n²) brute force into O(n) efficiency
• The “lookup pattern” powers dozens of problems

🚀 Final Thought

Master this pattern once, and many “new” problems will start to feel familiar.