LeetCode 1 – Two Sum

Two Sum is the first problem on LeetCode and still the most common warm-up in a phone screen. It is not really a test of whether you can find two numbers — it is a test of whether you reach for a hash map the moment you catch yourself writing a nested loop.

The problem

Given an array of integers and a target, return the indices of the two numbers that add up to that target. Exactly one such pair exists, and you may not use the same element twice.

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

Input:  nums = [3, 2, 4],     target = 6
Output: [1, 2]            not [0, 0] — an element cannot be reused

The brute force, and why it is not the answer

Try every pair: for each i, scan every j > i. That is O(n²) time and it is correct. Say it out loud in an interview, then improve it — the whole point of the problem is the improvement.

The reason the nested loop is wasteful is that the inner loop asks the same question every time: "is target - nums[i] somewhere in this array?". Membership questions are what hash tables are for.

The idea: remember what you have already walked past

Walk the array once, keeping a map from value → index of everything seen so far. At each element, the number that would complete the pair is target - nums[i]. If it is already in the map, the pair is found and you have both indices.

The ordering matters: look up before you insert. Checking first is what stops the element from pairing with itself when target happens to be 2 * nums[i] — for nums = [3, 2, 4], target = 6, the 3 is not yet in the map when it is examined, so it cannot match itself.

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();   // value -> index

        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]);      // look up first...
            if (j != null) {
                return new int[] { j, i };
            }
            seen.put(nums[i], i);                        // ...then insert
        }

        return new int[0];   // unreachable: the problem guarantees one solution
    }
}

Python

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen: dict[int, int] = {}          # value -> index

        for i, n in enumerate(nums):
            if target - n in seen:         # look up first...
                return [seen[target - n], i]
            seen[n] = i                    # ...then insert

        return []

Complexity

One pass is enough. A common first attempt fills the map completely and then does a second pass to query it; that is also O(n), but it needs an extra j != i guard to stop an element matching itself, and it breaks quietly on duplicates.

The sorted variant, and why it is a different problem

If the interviewer says the array is already sorted — or asks the follow-up "what if we only had to return the values, not the indices?" — the two-pointer answer becomes the better one, because it uses O(1) extra space:

// Only valid when nums is sorted, and only if VALUES are wanted, not original indices.
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
    int sum = nums[lo] + nums[hi];
    if (sum == target) return new int[] { lo, hi };
    if (sum < target) lo++;
    else hi--;
}

Sorting the input yourself to use this costs O(n log n) and destroys the original positions, so you would have to keep a copy of the array to recover the indices the problem actually asks for. That is strictly worse than the hash map here — but it is exactly the technique 3Sum is built on, which is why it is worth having in your hands.

What the interviewer is checking

• That you notice the nested loop is asking a membership question, and swap it for a hash map.
• That you handle target = 2 * nums[i] without letting an element pair with itself.
• That duplicates in the input do not break you. [3, 3], target = 6 returns [0, 1] — the second 3 finds the first in the map before overwriting its index.
• That you state the complexity of both versions unprompted.