yaohwang.com

Problem Overview

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

Solution 1: Brute Force Approach

How It Works

The brute force approach is straightforward: check every possible pair of numbers in the array.

for i in range(n):
    for j in range(i + 1, n):
        if nums[i] + nums[j] == target:
            return [i, j]

Complexity Analysis

• Time Complexity: O(n²) – We iterate through all pairs, which is n(n-1)/2 operations
• Space Complexity: O(1) – Only using a constant amount of extra space

When to Use

• Simple and easy to understand
• Good for small input sizes
• No extra memory overhead
• Not recommended for large arrays due to quadratic time complexity

Solution 2: Hash Map Approach

How It Works

Instead of checking pairs, we use a hash map (dictionary) to store numbers we’ve seen along with their indices. For each number, we check if its complement (target – current number) exists in the map.

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

Key Insight

The complement of a number num is target - num. If we’ve already seen the complement, we’ve found our pair!

Complexity Analysis

• Time Complexity: O(n) – Single pass through the array
• Space Complexity: O(n) – Hash map stores up to n elements

When to Use

• Recommended for most cases
• Efficient for large input sizes
• Linear time complexity makes it scalable
• Trade-off: uses extra memory for the hash map

Comparison

Takeaway

The hash map approach demonstrates a classic time-space trade-off: we use extra memory to achieve linear time complexity, making it the optimal solution for the Two Sum problem.