LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Hash Map/Two Sum Hash Map Pattern: Master Complement Search in O(n)

Two Sum Hash Map Pattern: Master Complement Search in O(n)

LeetCopilot Team
Dec 22, 2025
14 min read
Hash MapTwo SumComplement SearchInterview Prep
Go beyond memorizing Two Sum. Learn the complement search mental model, when hash maps beat two pointers, how to handle duplicates, and extend to 3Sum/4Sum problems.
Complete Guide

Hash Map Pattern: Complete Guide With Templates (Python/Java/JS)

Master the hash map pattern beyond basic dictionaries. Learn all 6 core patterns, recognition strategies, multi-language templates, and the decision framework that turns O(n²) brute force into O(n) elegance.

Read the complete guide

Two Sum is the most famous LeetCode problem (#1). It's often the first hash map problem people learn. But here's the trap:

Most people memorize the solution without understanding the pattern.

They can solve Two Sum, but when they see "3Sum" or "Pair with Difference K" or "4Sum II", they freeze. They don't recognize that these are all complement search problems—the same pattern, different variations.

This guide will teach you the complement search mental model that unlocks not just Two Sum, but an entire family of problems. You'll learn:

  • The complement search intuition (why hash maps work here)
  • When to use hash maps vs. two pointers for sum problems
  • How to handle duplicates correctly
  • The one-pass vs. two-pass approach
  • How to extend to 3Sum, 4Sum, and beyond
  • Common mistakes and edge cases

Master this pattern, and you'll never freeze on a sum problem again.

The Complement Search Mental Model

The core insight

For every element num, ask:

"Have I seen the complement (target - num) before?"

If yes, you found a pair. If no, remember this number for future complements.

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

text
i=0: num=2, complement=9-2=7
     Have I seen 7? No.
     Remember: {2: 0}

i=1: num=7, complement=9-7=2
     Have I seen 2? Yes! At index 0.
     Found: [0, 1]

Why hash map is perfect here

Without hash map (brute force):

python
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

With hash map:

python
seen = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i
# O(n) time, O(n) space

Trade-off: Spend O(n) space to save O(n²) → O(n) time.

The mental model

Think of the hash map as your memory:

  • As you scan left to right, you remember every number you've seen
  • For each new number, you check: "Is its complement in my memory?"
  • If yes, you found a pair
  • If no, add this number to memory for future lookups

This mental model extends to many problems beyond Two Sum.

When to Use Hash Map vs. Two Pointers

This is a critical decision point in interviews.

The decision rule

code
Is the array sorted?
├─ Yes → Use two pointers (O(1) space)
└─ No → Use hash map (O(n) space)

Can you sort the array?
├─ Yes, and order doesn't matter → Sort + two pointers
└─ No, need to preserve indices → Hash map

Hash map approach (unsorted)

When to use:

  • Array is unsorted
  • Need to return indices (not values)
  • Can't modify the array

Complexity: O(n) time, O(n) space

Example: Two Sum (#1)

Two pointers approach (sorted)

When to use:

  • Array is sorted (or can be sorted)
  • Need to return values (not indices)
  • Want O(1) space

Complexity: O(n) time, O(1) space (or O(n log n) if sorting needed)

Example: Two Sum II (#167)

Comparison

AspectHash MapTwo Pointers
TimeO(n)O(n) or O(n log n) with sort
SpaceO(n)O(1)
Sorted?NoYes
Return indices?YesNo (indices change after sort)
Handles duplicates?YesYes

For detailed comparison, see Hash Map vs Two Pointers.

The Universal Template

Python: One-Pass Approach (Recommended)

python
def twoSum(nums: List[int], target: int) -> List[int]:
    """
    Find two numbers that sum to target.
    Returns indices of the two numbers.
    
    Time: O(n)
    Space: O(n)
    """
    seen = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        # Check if complement exists
        if complement in seen:
            return [seen[complement], i]
        
        # Add current number to seen
        seen[num] = i
    
    return []  # No solution found

Key points:

  • Check for complement before adding current number
  • This handles duplicates correctly (see below)
  • Store index as value (problem asks for indices)

Python: Two-Pass Approach

python
def twoSum(nums: List[int], target: int) -> List[int]:
    # Pass 1: Build hash map
    seen = {}
    for i, num in enumerate(nums):
        seen[num] = i
    
    # Pass 2: Find complement
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen and seen[complement] != i:
            return [i, seen[complement]]
    
    return []

Pros: Clearer separation of concerns
Cons: Two passes instead of one, need to check seen[complement] != i

Recommendation: Use one-pass in interviews (more efficient, cleaner).

Java Template

java
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        
        if (seen.containsKey(complement)) {
            return new int[] {seen.get(complement), i};
        }
        
        seen.put(nums[i], i);
    }
    
    return new int[] {};  // No solution
}

JavaScript Template

javascript
function twoSum(nums, target) {
  const seen = new Map();
  
  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 [];
}

Handling Duplicates Correctly

This is where most people make mistakes.

The Problem

What if nums = [3, 3] and target = 6?

❌ Wrong approach (add before checking):

python
seen = {}
for i, num in enumerate(nums):
    seen[num] = i  # Add first
    complement = target - num
    if complement in seen:
        return [seen[complement], i]

# i=0: seen={3:0}, complement=3, found! return [0, 0] ❌ (same index!)

✅ Correct approach (check before adding):

python
seen = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i  # Add after checking

# i=0: complement=3, not in seen, add {3:0}
# i=1: complement=3, in seen! return [0, 1] ✓

Why It Works

By checking before adding:

  • At i=0: We haven't added 3 yet, so we don't find it
  • At i=1: We find the 3 from i=0, return [0, 1]

This naturally handles the case where target = 2 * num.

Edge Case: Multiple Pairs

What if there are multiple valid pairs?

python
nums = [1, 2, 3, 4], target = 5
# Valid pairs: [1,4] and [2,3]

The template returns the first valid pair found (left to right).

If you need all pairs, modify to collect instead of return:

python
def twoSumAll(nums, target):
    seen = {}
    pairs = []
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            pairs.append([seen[complement], i])
        seen[num] = i
    
    return pairs

For more on duplicates, see Handling Duplicates in Hash Maps.

Variations & Extensions

Variation 1: Two Sum II - Sorted Array (#167)

Problem: Same as Two Sum, but array is sorted.

Optimal approach: Two pointers (O(1) space)

python
def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

Why two pointers is better here:

  • Array is sorted → can use two pointers
  • O(1) space vs. O(n) for hash map
  • Still O(n) time

Variation 2: Two Sum III - Data Structure Design (#170)

Problem: Design a data structure that supports:

  • add(number): Add number to internal data structure
  • find(value): Return true if there exists any pair that sums to value
python
from collections import defaultdict

class TwoSum:
    def __init__(self):
        self.nums = defaultdict(int)
    
    def add(self, number: int) -> None:
        self.nums[number] += 1
    
    def find(self, value: int) -> bool:
        for num in self.nums:
            complement = value - num
            
            if complement in self.nums:
                # If complement == num, need at least 2 occurrences
                if complement == num:
                    if self.nums[num] >= 2:
                        return True
                else:
                    return True
        
        return False

Key insight: Store frequencies to handle duplicates.

Variation 3: Two Sum - Less Than K (#1099)

Problem: Find the maximum sum of two numbers that is less than k.

python
def twoSumLessThanK(nums: List[int], k: int) -> int:
    nums.sort()
    left, right = 0, len(nums) - 1
    max_sum = -1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum < k:
            max_sum = max(max_sum, current_sum)
            left += 1
        else:
            right -= 1
    
    return max_sum

Note: Two pointers is better here (need to try multiple pairs).

Variation 4: Pair with Difference K

Problem: Find if there exists a pair with difference k.

python
def findPair(nums: List[int], k: int) -> bool:
    seen = set()
    
    for num in nums:
        # Check both num + k and num - k
        if num + k in seen or num - k in seen:
            return True
        seen.add(num)
    
    return False

Pattern: Same complement search, but check num ± k.

Extending to 3Sum and 4Sum

The complement search pattern extends to k-sum problems.

3Sum (#15)

Problem: Find all unique triplets that sum to zero.

Approach: Fix one number, use Two Sum on the rest.

python
def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates for first number
        if i > 0 and nums[i] == nums[i-1]:
            continue
        
        # Two Sum on remaining array
        left, right = i + 1, len(nums) - 1
        target = -nums[i]
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result

Pattern: 3Sum = Fix one + Two Sum (with two pointers)

Why not hash map for inner loop?

  • Array is sorted (for deduplication)
  • Two pointers is O(1) space
  • Need to avoid duplicates (easier with two pointers)

4Sum II (#454)

Problem: Count tuples (i, j, k, l) where A[i] + B[j] + C[k] + D[l] == 0.

Approach: Split into two pairs, use hash map.

python
from collections import defaultdict

def fourSumCount(A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
    # Count all possible sums of A[i] + B[j]
    ab_sums = defaultdict(int)
    for a in A:
        for b in B:
            ab_sums[a + b] += 1
    
    # For each C[k] + D[l], check if -(C[k] + D[l]) exists in ab_sums
    count = 0
    for c in C:
        for d in D:
            complement = -(c + d)
            count += ab_sums[complement]
    
    return count

Pattern: 4Sum II = Two pairs + complement search

Complexity: O(n²) time, O(n²) space

Common Mistakes

Mistake 1: Adding Before Checking

❌ Wrong:

python
seen[num] = i
if target - num in seen:
    return [seen[target - num], i]

Why it fails: When target = 2 * num, you find the same element.

✅ Correct:

python
if target - num in seen:
    return [seen[target - num], i]
seen[num] = i

Mistake 2: Wrong Key/Value Pair

❌ Wrong:

python
seen[i] = num  # Storing index as key!

Why it fails: You need to look up by value, not by index.

✅ Correct:

python
seen[num] = i  # Store value as key, index as value

Mistake 3: Not Handling No Solution

❌ Wrong:

python
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    # No return statement!

✅ Correct:

python
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []  # Or raise exception, depending on problem

Mistake 4: Using Hash Map When Two Pointers Is Better

❌ Suboptimal:

python
# Two Sum II (sorted array) with hash map
def twoSum(numbers, target):
    seen = {}
    for i, num in enumerate(numbers):
        if target - num in seen:
            return [seen[target - num] + 1, i + 1]
        seen[num] = i
# O(n) time, O(n) space

✅ Optimal:

python
# Use two pointers for sorted array
def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]
        elif s < target:
            left += 1
        else:
            right -= 1
# O(n) time, O(1) space

Edge Cases to Test

1. Empty Array

python
nums = [], target = 0
# Should return [] (no solution)

2. Single Element

python
nums = [1], target = 2
# Should return [] (need two elements)

3. Duplicates (target = 2 * num)

python
nums = [3, 3], target = 6
# Should return [0, 1] ✓

4. No Solution

python
nums = [1, 2, 3], target = 10
# Should return []

5. Negative Numbers

python
nums = [-1, -2, -3, -4], target = -6
# Should return [1, 3] (-2 + -4 = -6)

6. Zero

python
nums = [0, 4, 3, 0], target = 0
# Should return [0, 3] (0 + 0 = 0)

Complexity Analysis

Time Complexity

Hash map approach: O(n)

  • Single pass through array
  • Each lookup/insert is O(1) average

Two pointers approach (sorted): O(n)

  • Single pass with two pointers
  • If sorting needed: O(n log n)

Space Complexity

Hash map approach: O(n)

  • Store up to n elements in hash map

Two pointers approach: O(1)

  • Only two pointers, no extra space

Trade-offs

ApproachTimeSpaceWhen to Use
Hash mapO(n)O(n)Unsorted, need indices
Two pointersO(n)O(1)Sorted, don't need indices

Practice Problems

Beginner

  1. Two Sum (#1) - Classic hash map
  2. Two Sum II (#167) - Two pointers (sorted)
  3. Two Sum III (#170) - Data structure design
  4. Two Sum IV - BST (#653) - Hash set variant

Intermediate

  1. 3Sum (#15) - Fix one + two pointers
  2. 3Sum Closest (#16) - Fix one + two pointers
  3. 4Sum (#18) - Fix two + two pointers
  4. 4Sum II (#454) - Two pairs + hash map
  5. Two Sum Less Than K (#1099) - Two pointers

Advanced

  1. Subarray Sum Equals K (#560) - Prefix sum + hash map
  2. Count Pairs with Difference K - Hash set
  3. Find K Pairs with Smallest Sums (#373) - Heap + hash map

Summary

The Two Sum pattern is the foundation of complement search problems.

Key principles:

  • Complement search: For each element, check if target - element exists
  • Check before adding: Handles duplicates correctly
  • Hash map vs two pointers: Unsorted → hash map, sorted → two pointers
  • Extend to k-sum: Fix elements, reduce to smaller problem

The template:

python
seen = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i
return []

When to use:

  • ✅ Find pairs that sum to target
  • ✅ Unsorted array
  • ✅ Need indices
  • ✅ Can use O(n) space

When NOT to use:

  • ❌ Array is sorted (use two pointers)
  • ❌ Need O(1) space (use two pointers)
  • ❌ Finding all pairs (use two pointers for deduplication)

Common mistakes:

  • ❌ Adding before checking
  • ❌ Wrong key/value pair
  • ❌ Not handling no solution
  • ❌ Using hash map when two pointers is better

Next steps:

  1. Master the complete hash map guide
  2. Learn hash map vs two pointers decision framework
  3. Study handling duplicates
  4. Practice the beginner problem set

Master Two Sum, and you unlock an entire family of complement search problems.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials