Two Sum — LeetCode #1 (Easy)

TL;DR

Single-pass hash map lookup: store each number's index as you go, check for the complement before storing. O(n) time, O(n) space.

The Problem

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

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

The answer is indices 0 and 1 because nums[0] + nums[1] == 9. Note: return indices, not values.

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Exactly one valid answer exists.

Naive Approach

Fix one number, scan every number after it for the complement. Repeat for each starting index.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

O(n²) time, O(1) space — ~50 million pair checks on a 10,000-element array.

Key Insight

At every index i, you already know the complement you need: target - nums[i]. The only question is whether that value appeared earlier. Instead of scanning backwards, keep a hash map that answers "have I seen value v?" in O(1).

Two things to get right: use the value as the key and the index as the value (you look up by value, you want to retrieve the index); and check the map before inserting the current number, so a value can't match itself.

Optimal Solution

One pass. For each element, compute need = target - x. If need is already in seen, you're done. Otherwise, record x → i and continue.

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i

Step-by-step on [2, 7, 11, 15], target 9:

1. i=0, x=2 — need=7. seen={}, not found. Store seen[2]=0.
2. i=1, x=7 — need=2. seen={2:0}, found. Return [seen[2], 1] → [0, 1].

The loop never reaches indices 2 or 3.

Complexity

Approach	Time	Space
Naive (nested loops)	O(n²)	O(1)
Hash map (one pass)	O(n)	O(n)

Pattern Recognition

This is the complement lookup pattern: when a problem asks for a pair satisfying some condition, storing what you've seen in a hash map turns a second scan into a O(1) lookup. You'll find the same structure in 3Sum (reduce to Two Sum), subarray sum equals k, and any problem where "what do I need to complete this?" has a clear formula.

In Interviews

The brute force buys you nothing here — interviewers expect the hash map solution immediately. What they're actually watching for: correct key/value orientation in the map, and the check-before-insert rule (if seen[x] = i runs before the lookup, x + x == target would return [i, i] — wrong).

Common follow-ups:

• What if multiple valid pairs exist — return all of them? Collect results instead of returning early; decide whether to deduplicate.
• What if the array is sorted? Two-pointer from both ends achieves O(n) time with O(1) space — no hash map needed.

---

📺 Watch the full walkthrough on YouTube: https://youtu.be/4JUNrRN16gM