🟩 Two Sum (#1)

🔗 Problem Link

• Leetcode 1: Two Sum
• Neetcode: Two Sum

📋 Problem Statement

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 that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

💡 Examples

Example 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Example 3

Input: nums = [3,3], target = 6
Output: [0,1]

⚠️ Constraints

• Only one valid answer exists.

🔑 Key Insights & Approach

Core Observation: For each number, instead of checking every other number (O(n²)), we can ask: "Have I already seen the complement that would sum to target?" This transforms the problem into a lookup operation.

The Key Question: For current number n, does target - n exist in what we've seen so far?

Why Hash Map?

• Instant lookup: Checking if complement exists is O(1) instead of O(n)
• Store indices: We need to return positions, not just values
• Single pass possible: We can check and store simultaneously

The Mental Model:

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

i=0, n=2: diff=7, seen={}           → not found, add {2:0}
i=1, n=7: diff=2, seen={2:0}        → found! return [0,1]

Two Implementation Styles:

1. Two-pass: Build entire map first, then search (clearer logic)
2. One-pass: Check for complement before adding current number (more efficient, prevents self-pairing)

Why One-Pass Works: Since we're looking for a pair, when we reach the second number of a valid pair, the first number is already in our map. No need to process all numbers first.

Pattern Recognition: This is the "Complement Lookup" pattern — instead of nested loops, use a hash map to find "what's missing" in O(1) time.

🐍 Solution: Python

Approach 1: Hash Map (Two Pass)

Time Complexity: O(n) | Space Complexity: O(n)

def twoSum(self, nums: List[int], target: int) -> List[int]:
    indices = {}  # val -> index

    for i, n in enumerate(nums):
        indices[n] = i

    for i, n in enumerate(nums):
        diff = target - n
        if diff in indices and indices[diff] != i:
            return [i, indices[diff]]
    return []

Approach 2: Hash Map (One Pass)

Time Complexity: O(n) | Space Complexity: O(n)

def twoSum(self, nums: List[int], target: int) -> List[int]:
    prevMap = {}  # val -> index

    for i, n in enumerate(nums):
        diff = target - n
        if diff in prevMap:
            return [prevMap[diff], i]
        prevMap[n] = i

🔵 Solution: Golang

📚 References

• YouTube: Two Sum - Leetcode 1 - Python