3. Arrays & Hashing — Two Sum

🔗 NeetCode 150 | Two Sum

🧩 Problem

Image 1

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] === target and i != j.

You may assume every input has exactly one valid answer.

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• Exactly one valid answer exists
• Target: O(n) time, O(n) space

❌ Naive Solution

The first instinct — two nested loops, check every pair:

twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (nums[i] + nums[j] === target && i !== j) {
                return [i, j];
            }
        }
    }
    return [];
}

Why it fails: Two nested loops = O(n²) time. It works — but interviewer will immediately ask for something better. For 1⁰⁴ elements that’s 100 million operations.

✅ Optimal Solution

Pattern: HashMap (value → index)

Think of it like two brothers in a family. You’re walking through the array and for each number you meet — you ask: “Where is your brother? The one that adds up to the target?”

That missing brother is complement = target - nums[i].

If the brother is already in the Map — you found the pair. If not — save the current number and move on.

twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>(); // value -> index
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (seen.has(complement)) {
            return [seen.get(complement)!, i];
        }
        seen.set(nums[i], i);
    }
    return [];
}

Step by step with nums = [3,4,5,6], target = 7:

• i=0 → complement = 7-3 = 4 → not in Map → save {3: 0}
• i=1 → complement = 7-4 = 3 → found in Map at index 0 → return [0, 1] ✅

One pass. Done.

📊 Complexity

ComplexityTimeO(n)SpaceO(n)

💡 Key Takeaway

Whenever you need to find a pair that satisfies a condition — store what you’ve seen in a Map and look up the complement in O(1). One loop is enough.

You’ll use this same pattern in: Three Sum, Four Sum, Subarray Sum Equals K.