LeetCode Solution 1. Two Sum

Problem Description

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.

Example:

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

Solution 1: Brute Force

Approach

The most intuitive method is to use two nested loops to check all possible pairs of numbers.

Code

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

Complexity Analysis

• Time Complexity: O(n²)

  • Outer loop runs n times
  • For each element, inner loop runs n/2 times on average
  • Total: approximately n × n/2 = O(n²)

• Space Complexity: O(1)

  • Only uses constant variables (i, j), doesn’t scale with input size

Pros and Cons

• ✅ Simple and intuitive, easy to understand and implement
• ✅ No extra space required
• ❌ Low time efficiency, very slow for large arrays

Solution 2: Two-Pass Hash Table

Approach

Use a Hash Table to reduce lookup time from O(n) to O(1).

1. First pass: Build a mapping from each number to its index
2. Second pass: Check if each number’s complement exists

Code

def twoSum(nums, target):
    # First pass: build hash table
    hashmap = {}
    for i in range(len(nums)):
        hashmap[nums[i]] = i
    
    # Second pass: look for complement
    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in hashmap and hashmap[complement] != i:
            return [i, hashmap[complement]]
    
    return []

Complexity Analysis

• Time Complexity: O(n)

  • First pass: n insertions, each O(1) = O(n)
  • Second pass: n lookups, each O(1) = O(n)
  • Total: O(n) + O(n) = O(n)

• Space Complexity: O(n)

  • Hash table stores at most n key-value pairs

Key Understanding: Why is Hash Table lookup O(1)?

Hash Table uses a hash function to directly calculate the storage location of elements, no need for sequential comparison:

Looking up 7 in hashmap:
1. Calculate hash(7) = some position
2. Directly access that position
3. No need to traverse the entire table!

Solution 3: One-Pass Hash Table (Optimal Solution)

Approach

Search while traversing, completing everything in a single loop:

1. First check if the current number’s complement is already in the hash table
2. If not, add the current number to the hash table

Code

def twoSum(nums, target):
    hashmap = {}
    for i in range(len(nums)):
        complement = target - nums[i]
        
        # Search first
        if complement in hashmap:
            return [hashmap[complement], i]
        
        # Add later
        hashmap[nums[i]] = i
    
    return []

Algorithm Process Example

Array: [2, 7, 11, 15], Target: 9

i=0, nums[0]=2:
  - complement = 9-2 = 7
  - Is 7 in hashmap? No
  - Add: hashmap = {2: 0}

i=1, nums[1]=7:
  - complement = 9-7 = 2
  - Is 2 in hashmap? Yes! At position 0
  - Return [0, 1] ✓

Complexity Analysis

• Time Complexity: O(n)

  • Worst case traverses the entire array once
  • Lookup and insertion in each iteration are O(1)

• Space Complexity: O(n)

  • Worst case hash table stores n-1 elements

Why Does This Work?

Key insight: For any solution pair (i, j), when we traverse to the larger index, the smaller index is already in the hash table!

Comparison of Three Solutions

Key Takeaways

1. Time-Space Tradeoff: We trade O(n) extra space for time efficiency improvement from O(n²) to O(n)
2. Power of Hash Table: Reducing lookup operation from O(n) to O(1) is key to many algorithm optimizations
3. Levels of Algorithm Optimization:
   • Step 1: Implement functionality (brute force)
   • Step 2: Optimize time complexity (Hash Table)
   • Step 3: Optimize actual execution efficiency (one-pass)

Practice Suggestions

1. First implement the brute force solution yourself to ensure understanding of the problem
2. Think about how to optimize the lookup process
3. Try to manually simulate how the Hash Table works
4. Compare actual execution times of different solutions on large datasets

This problem is a classic example for understanding Hash Table applications. Mastering the evolution of these three solutions is very helpful for solving other similar problems!