The O(n) Club: Two Sum Problem: Where Indices Are the Real MVP

The O(n) Club: Two Sum Problem — Where Indices Are the Real MVP

⚡ TL;DR

You get an array and a target. Find two elements whose indices sum up to the target—not the values, the indices. Yes, seriously. Brute-force works only if you really want to test your interviewer’s patience. Prefer hash map magic in Java:

// Brute force approach: Like searching for your keys in a haystack ... with a blindfold.
for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] == target) return new int[]{i, j};
    }
}
// Works fine for tiny arrays and massive caffeine reserves

🧠 How Devs Usually Mess This Up

Honestly, it’s almost a rite of passage. You’ll see folks:

🔍 What’s Actually Going On

Imagine shopping with a gift card and you want to spend every cent. Are you:

🛠️ PseudoCode

• Initialize a hash map:
  Map<Integer, Integer> seen = new HashMap<>(); — Think of it as your algorithmic sticky note.
• Loop through the array:
  for (int i = 0; i < nums.length; i++) { ... }
• Calculate complement:
  What number do you need to hit the target with your current number?
  int complement = target - nums[i];
• If complement is in the map:
  Congrats: you found the answer fast. Return those two indices.
  if (seen.containsKey(complement)) return new int[]{seen.get(complement), i};
• Else, put your number and index into the map for next time.
  seen.put(nums[i], i);
• Keep going till you hit jackpot. Or the end of the array.

💻 The Code

// This is peak O(n) elegance.
import java.util.HashMap;
import java.util.Map;
 public class TwoSum {
    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);
        }
        throw new IllegalArgumentException("Not found. Try buying fewer snacks!");
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Duplicate numbers? Sure! [3, 3] works for target = 6. As long as indices aren’t identical, you’re golden.
• Returning numbers instead of indices? Don’t. Your next interviewer could be allergic.
• Edge cases: Arrays of size < 2, or no valid pairs—throw a tantrum, err, IllegalArgumentException.
• Time & space: Hash map gives O(n) speed for O(n) extra memory. Brute force: O(n²), aka a leisurely stroll compared to the Ferrari.

🧠 Interviewer Brain-Tattoo

Hash maps: because every developer wants to look clever and still make it home by dinner.