Two Sum

Problem

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

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]

Example 3:

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

Constraints:

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

Solution

Approach: Hash Map (One Pass)

The key insight is to use a hash map to store numbers we’ve seen along with their indices. As we iterate through the array, for each number, we check if its complement (target - current number) exists in the hash map. If it does, we’ve found our pair. If not, we add the current number to the hash map and continue.

This approach is more efficient than the brute force solution (checking all pairs with nested loops), which would be O(n²).

Implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}  # Maps number -> index

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

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

            seen[num] = i

        return []  # Should never reach here given constraints

Alternative (Two Pass):

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # First pass: build hash map
        seen = {num: i for i, num in enumerate(nums)}

        # Second pass: check for complement
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen and seen[complement] != i:
                return [i, seen[complement]]

        return []

Complexity Analysis

Time Complexity: O(n), where n is the length of the array. We iterate through the array once, and hash map lookups are O(1) on average.
Space Complexity: O(n) in the worst case, where we store all n elements in the hash map before finding the solution.

Key Insights

Complement Thinking: Instead of checking if nums[i] + nums[j] == target, think about whether target - nums[i] exists in the array. This transforms a two-element search into a single-element lookup.
One Pass vs Two Pass: The one-pass solution is more elegant and slightly more efficient. We build the hash map while searching, rather than building it completely first.
Hash Map for O(1) Lookup: Using a hash map gives us constant-time lookups, avoiding the O(n²) nested loop approach.
Index Tracking: We store indices (not just the numbers themselves) because the problem asks for indices in the output.
No Duplicate Use: The condition seen[complement] != i in the two-pass solution ensures we don’t use the same element twice. In the one-pass solution, this is inherently avoided because we check before adding to the map.