1. Two Sum

Approach 1: Two-Pass Hash Map

Algorithm:

First pass builds the full map
Second pass looks up complements
- Skipping the element itself

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

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

        return []

Time: $O(n)$ — two linear passes.
Space: $O(n)$ — the value→index map.

Approach 2: One-Pass Hash Map

Why one-pass is sufficient:

The valid answer is some pair (i, j) where i < j.
When the loop reaches index j, index i has already been visited and stored in the map.

The one-pass approach avoids the self-use edge case entirely.

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

        return []

Time: $O(n)$ — single pass over the array.
Space: $O(n)$ — the hash map of seen values.

Takeaway

Approach	Time	Space
Brute Force	$O(n^2)$	$O(1)$
Two-Pass Hash Map	$O(n)$	$O(n)$
One-Pass Hash Map	$O(n)$	$O(n)$

The one-pass hash map is optimal: it matches the best time complexity while making a single traversal and handling the duplicate-index case cleanly.

Last updated on

1. Two Sum

Approach 1: Two-Pass Hash Map

Approach 2: One-Pass Hash Map

Takeaway

On this page