Cracking the Two Sum Interview: From Brute Force to Hash Map Optimization

Self‑introduction: Hello everyone, I’m Xuanwu. Starting today I leave campus and begin my interview series, tackling one algorithm each day and recording my growth.

Me: Hello interviewer, I don’t know much about algorithms, I’ve only solved LeetCode problem #1, so please don’t ask anything too hard. I’m ready.

Interviewer: Alright, let’s start with LeetCode problem #1. Given an integer array nums and an integer target, find the two numbers whose sum equals target and return their indices. Assume exactly one solution exists and you cannot use the same element twice.

Example:

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

Me: The problem is simple; a double for‑loop solves it. The outer loop iterates over the array, the inner loop compares the current element with the following elements to avoid duplicate calculations.

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            // inner loop only checks numbers after i
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}

Interviewer: Not bad, you avoided checking previous elements. But the time complexity is O(n²). Can you reduce it?

Me: Yes, we can lower the complexity by eliminating repeated work. By traversing the array once and storing each value’s index in a hash map, we can look up the complement in O(1) time during a second pass.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap();
        // First pass: put all numbers into the map
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        // Second pass: check if the complement exists
        for (int i = 0; i < nums.length; i++) {
            int one = nums[i]; // first number
            int two = target - one; // second number
            if (map.containsKey(two)) {
                return new int[]{i, map.get(two)};
            }
        }
        return new int[]{};
    }
}

Interviewer: If the array is [... ] and target = 6, your code returns an incorrect result because the current element is still in the map.

Me: Right, we need to remove the current element from the map before checking.

for (int i = 0; i < nums.length; i++) {
    int one = nums[i];
    int two = target - one;
    if (map.get(one) == i) map.remove(one);
    if (map.containsKey(two)) {
        return new int[]{i, map.get(two)};
    }
}

Interviewer: Good. Can we improve further by building the map while iterating, so we never need to delete entries?

Me: Yes, we can check for the complement first, then store the current number.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int one = nums[i];
            int two = target - one;
            if (map.containsKey(two)) {
                return new int[]{i, map.get(two)};
            }
            map.put(one, i); // store after checking
        }
        return new int[]{};
    }
}

Interviewer: This avoids deletions and reduces the time complexity to O(n).

At that moment the interviewer's phone rang, and the interview ended.