The O(n) Club: Two Sum: The Algorithmic Riddle Every Dev Loves (to Hate)

The O(n) Club: Two Sum—The Algorithmic Riddle Every Dev Loves (to Hate)

⚡ TL;DR

Two Sum: Given an integer array, find the indices of two numbers that add up to a target. Brute force is for those auditioning for a time-wasting contest; hash map is for those who like jobs.

// Brute force: The two-for-loop special
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};
    }
}

🧠 How Devs Usually Mess This Up

Every developer has tried to impress the interviewer by ‘optimizing’ nonsense—or has simply misread the question. Classic ways to bungle Two Sum:

• Returning values not indices: You want the barcode, not the price tag! Indices, please. Don’t be that person.
• Using the same index twice: Unless you work in a quantum array, the same element can’t be in two places at once.
• Assuming multiple answers: Read the rules: exactly one pair exists. This is not the time to show how thorough you can be.

🔍 What’s Actually Going On

Imagine you’re a cashier hunting for two receipts that match the nightly till (minus snacks for stress). Brute force is like checking every combination—good for insomnia, bad for runtime. The smart move is to keep a cheat-sheet (hello, HashMap): Every time you scan a number, you check—did I already see what it needs to reach the target? If yes, you cash out; if not, you keep looking. Your CPU thanks you, your boss thanks you, your coffee cools down.

🛠️ PseudoCode

• Create a HashMap to store numbers as you scan them.
• Loop through the array one number at a time:
  • Let complement = target - current number.
  • If complement is already in the HashMap:

    return new int[] { map.get(complement), current index };

    Celebrate appropriately.
  • Else, put the current number and its index in the map:

    map.put(current number, current index);

💻 The Code

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t return the same index twice—unless you want a special message from your interviewer.
• Return the indices, not the array values (unless you like revision requests).
• Default version = 1 solution. Variants ask for more pairs—read the prompt like it’s your job offer letter.
• Brute force: O(n²) and O(1) space. Hash map: O(n) and O(n) space. The trade: a little memory for much happiness.

🧠 Interviewer Brain-Tattoo

“If you forget Two Sum’s HashMap trick in an interview, may runtime errors haunt your dreams (and your next whiteboard).”