🧠 Two Sum – Brute Force vs Hashing

✅ Problem Statement

Imagine you have a list of numbers and a target number. Your goal is to find the two numbers that sum up to the target and return their indices.

This is more than just numbers: it’s about pattern recognition, logical thinking, and efficiency. You will see two ways to solve it: brute-force (straightforward but slow) and hashing (smart and fast).

🧩 Example

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

Think of this as a pair-finding puzzle. You can try every combination, or you can be clever and remember what you've seen.

🔍 Approach 1: Brute Force (O(n²))

What: Try all pairs (i, j) to see if they add up to the target. Why: It’s simple and guarantees a solution if it exists. How: Use two nested loops, checking each possible pair.

🐍 Python Code

def two_sum_brute(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]

Thought Process:

1. Start at the first number.
2. Check it with every number after it.
3. If the sum equals the target, return the indices.

Pros: Easy to implement, easy to reason about. Cons: Inefficient for large lists — imagine 10,000 numbers; you’d check 50 million pairs!

⚡ Approach 2: HashMap / Dictionary (O(n))

What: Keep track of numbers you’ve seen in a dictionary while scanning the list once. Why: Instead of checking every pair, ask: “Do I already have the number that pairs with the current one to make the target?” How: Store each number’s index in a dictionary. For each new number, check if target - num exists in the dictionary. If yes, return the indices.

🐍 Python Code

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

Think Like a Detective:

• You see the first number: remember it.
• You see the second: check if it completes a pair.
• Keep going until the puzzle is solved.

🧪 JavaScript Stack Trace Example

function twoSum(nums, target) {
  const seen = {};
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen[complement] !== undefined) {
      return [seen[complement], i];
    }
    seen[nums[i]] = i;
  }
  return [];
}

// Example
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target)); // Output: [0, 1]

Stack Trace / Execution Flow

i = 0, num = 2, complement = 7
  seen = {2: 0}           // complement not found, store 2

i = 1, num = 7, complement = 2
  seen = {2: 0, 7: 1}     // complement found at index 0
  return [0, 1]

🔍 Breaking It Down for Understanding

1. Brute-force: Treat the array like a grid of possibilities. Check everything. Guarantees correctness but slow.
2. Hashing: Treat the array as a memory game. Remember numbers as you go. Check if the current number completes a pair. Fast and elegant.

Key Insight: Instead of repeating work (checking all pairs), reuse information you already have. This is a general principle in algorithm design: trading memory for speed.

📝 Summary

Approach	Time Complexity	Space Complexity	Notes
Brute-force	O(n²)	O(1)	Simple, works always
Hashing	O(n)	O(n)	Uses memory to speed up search

---

💡 Teaching Perspective

• What: Find two numbers that sum to a target.
• Why: This introduces the power of remembering past computations (a foundation for hashmaps, caching, dynamic programming).
• How: First, brute-force. Then, observe patterns and optimize.
• Mental Model: Think like a detective — “Have I seen the other half of the pair?”
• Tip: Hashing is often the “expected solution” in interviews because it shows both problem-solving insight and code efficiency.