LeetCode 1: Two Sum - All Approaches Explained

Approach 1: Brute Force (Nested Loops)

Intuition

The simplest way to solve this is to check every possible pair of numbers in the array. For each number, pair it with every other number, calculate their sum, and see if it equals the target. If it does, return their indices. This is exhaustive and doesn’t use any extra data structures—just pure iteration.

How It Works

• Use two loops: an outer loop to pick the first number and an inner loop to pick the second.
• For each pair (nums[i], nums[j]), check if nums[i] + nums[j] == target.
• If true, return [i, j].

Step-by-Step Example

Let’s use nums = [2, 7, 11, 15] and target = 9:

• i = 0 (num = 2):
  • j = 0: 2 + 2 = 4 (no match)
  • j = 1: 2 + 7 = 9 (match! Return [0, 1])
  • (We could stop here, but let’s see the full process for clarity)
  • j = 2: 2 + 11 = 13
  • j = 3: 2 + 15 = 17
• i = 1 (num = 7): (continues if no early return)
  • j = 0: 7 + 2 = 9 (match again, but we’d already have stopped)

Python Code

Copy codedef twoSum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):          # Outer loop for first number
        for j in range(n):      # Inner loop for second number
            if i != j:          # Ensure we don’t use the same index
                if nums[i] + nums[j] == target:
                    return [i, j]
    return []  # No solution (though guaranteed one exists)

# Test cases
print(twoSum_brute_force([2, 7, 11, 15], 9))  # Output: [0, 1]
print(twoSum_brute_force([3, 2, 4], 6))      # Output: [1, 2]
print(twoSum_brute_force([3, 3], 6))         # Output: [0, 1]

Detailed Walkthrough

• Outer loop (i) : Runs from 0 to n-1.
• Inner loop (j) : Also runs from 0 to n-1, but we add if i != j to avoid pairing a number with itself (per the problem’s rule).
• For [2, 7, 11, 15] and target = 9:
  • Pair (0, 0): Skipped (i == j).
  • Pair (0, 1): 2 + 7 = 9. Found it! Return [0, 1].
• The if i != j check ensures we don’t accidentally use nums[0] + nums[0] in cases like [3, 3].

Complexity

• Time Complexity : O(n²). For each of the n elements, we check up to n others, giving n * n = n².
• Space Complexity : O(1). We only use a few variables, no extra data structures.

Pros and Cons

• Pros : Dead simple, no extra memory, easy to understand.
• Cons : Slow for large arrays (e.g., 10,000 elements means ~50 million comparisons).

Approach 2: Slightly Optimized Nested Loops

Intuition

The brute force checks every pair, including redundant ones (e.g., (0, 1) and (1, 0)). We can optimize slightly by ensuring the second index j starts after the first index i. This avoids checking the same pair twice and skips the i != j check since j will always be greater than i.

How It Works

• Outer loop picks nums[i].
• Inner loop starts at j = i + 1 instead of 0.
• Check nums[i] + nums[j] == target.

Step-by-Step Example

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

• i = 0 (num = 2):
  • j = 1: 2 + 7 = 9 (match! Return [0, 1])
  • j = 2: 2 + 11 = 13
  • j = 3: 2 + 15 = 17
• i = 1 (num = 7):
  • j = 2: 7 + 11 = 18
  • j = 3: 7 + 15 = 22
• (Stops early due to match at [0, 1])

Python Code

Copy codedef twoSum_slightly_optimized(nums, target):
    n = len(nums)
    for i in range(n):              # Outer loop
        for j in range(i + 1, n):   # Inner loop starts at i+1
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # No solution (though guaranteed one exists)

# Test cases
print(twoSum_slightly_optimized([2, 7, 11, 15], 9))  # Output: [0, 1]
print(twoSum_slightly_optimized([3, 2, 4], 6))      # Output: [1, 2]
print(twoSum_slightly_optimized([3, 3], 6))         # Output: [0, 1]

Detailed Walkthrough

• Outer loop (i) : 0 to n-1.
• Inner loop (j) : i+1 to n-1.
• For [3, 2, 4] and target = 6:
  • i = 0 (3):
    • j = 1: 3 + 2 = 5
    • j = 2: 3 + 4 = 7
  • i = 1 (2):
    • j = 2: 2 + 4 = 6 (match! Return [1, 2])
• Notice we don’t check (1, 0) or (2, 1), reducing redundant work.

Complexity

• Time Complexity : Still O(n²). We’re checking n-1 + n-2 + ... + 1 pairs, which is (n * (n-1)) / 2, still quadratic.
• Space Complexity : O(1). No extra space beyond variables.

Pros and Cons

• Pros : Slightly fewer comparisons than brute force, cleaner code (no i != j check).
• Cons : Still inefficient for large inputs, no significant improvement over brute force.

Approach 3: Hash Table (Optimal)

Intuition

Instead of checking every pair, use a hash table to store numbers we’ve seen and their indices. For each number, calculate its complement (target - num) and check if it’s in the hash table. If it is, we’ve found the pair. If not, add the current number and its index to the table and move on. This trades space for a massive time improvement.

How It Works

• Create an empty hash table (e.g., Python’s dict).
• For each nums[i]:
  • Compute complement = target - nums[i].
  • If complement is in the hash table, return [hash_table[complement], i].
  • Otherwise, add nums[i]: i to the hash table.

Step-by-Step Example

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

• Hash table starts empty: {}
• i = 0 (num = 2):
  • complement = 9 - 2 = 7
  • 7 not in hash table
  • Add 2:0 → {2: 0}
• i = 1 (num = 7):
  • complement = 9 - 7 = 2
  • 2 is in hash table (at index 0)
  • Return [0, 1]
• (Stops here)

For nums = [3, 3] and target = 6:

• Hash table: {}
• i = 0 (num = 3):
  • complement = 6 - 3 = 3
  • 3 not in hash table
  • Add 3:0 → {3: 0}
• i = 1 (num = 3):
  • complement = 6 - 3 = 3
  • 3 is in hash table (at index 0)
  • Return [0, 1]

Python Code

Copy codedef twoSum_hash_table(nums, target):
    seen = {}  # Hash table to store number:index pairs
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []  # No solution (though guaranteed one exists)

# Test cases
print(twoSum_hash_table([2, 7, 11, 15], 9))  # Output: [0, 1]
print(twoSum_hash_table([3, 2, 4], 6))      # Output: [1, 2]
print(twoSum_hash_table([3, 3], 6))         # Output: [0, 1]

Detailed Walkthrough

• Hash table (seen) : Maps numbers to their indices.
• enumerate : Gives us both index i and value num.
• For [3, 2, 4] and target = 6:
  • i = 0, num = 3:
    • complement = 6 - 3 = 3
    • seen = {3: 0}
  • i = 1, num = 2:
    • complement = 6 - 2 = 4
    • seen = {3: 0, 2: 1}
  • i = 2, num = 4:
    • complement = 6 - 4 = 2
    • 2 is in seen at index 1
    • Return [1, 2]
• The hash table lookup (in operation) is O(1) on average, making this fast.

Complexity

• Time Complexity : O(n). We traverse the array once, and hash table operations (insert, lookup) are O(1) average case.
• Space Complexity : O(n). The hash table stores up to n key-value pairs.

Pros and Cons

• Pros : Fast, scalable, elegant, and the go-to solution for interviews.
• Cons : Uses extra space, slightly more complex than brute force.

Comparison of Approaches

Edge Cases to Consider

1. Duplicates : [3, 3], target = 6. All approaches handle this since we check indices, not values.
2. Negative Numbers : [-1, -2], target = -3. Works fine—math still holds.
3. No Solution : Problem guarantees one, but hash table returns empty list if none found.

Final Thoughts

• Brute Force is a great starting point to understand the problem.
• Slightly Optimized shows how small tweaks can improve clarity, if not performance.
• Hash Table is the gold standard—learn it, love it, use it.

This problem is a gateway to more advanced topics like hash tables and trade-offs in algorithm design. Try coding it in other languages (like Java or C++) or tweaking it (e.g., what if there are multiple solutions?). Happy coding!