Two Sum

Problem Description

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

You can assume each input has exactly one solution, and you can’t use the same element twice. Order of the returned indices doesn’t matter.

Examples

Constraints

• 2 ≤ nums.length ≤ 10⁴
• -10⁹ ≤ nums[i] ≤ 10⁹
• -10⁹ ≤ target ≤ 10⁹
• Exactly one valid answer exists

The Trap Most People Fall Into First

The natural instinct is to check every pair of numbers against each other. That works, but it’s the kind of answer that stalls an interview rather than ending it. The real question this problem is testing isn’t “can you find two numbers that add up to a target,” it’s “do you know how to trade space for time.”

Once you see that, the problem turns into a single question: for each number, what value would I need to see earlier in the array to complete the pair? If you can answer that in O(1), you can solve the whole problem in one pass.

Solution 1: Brute Force

Check every pair. It’s the baseline, and it’s worth showing because interviewers want to see you can identify why it’s insufficient, not just that a better solution exists.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        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};
                }
            }
        }
        return new int[]{};
    }
}

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

#include <vector>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

Complexity Analysis:

• Time Complexity: O(n²): nested loop checks every pair.
• Space Complexity: O(1): no extra data structure.

Where it breaks: at n = 10⁴, that’s up to 100 million comparisons. It’ll pass on LeetCode’s test cases, but in a real interview, stopping here signals you haven’t thought about scale.

Solution 2: Hash Map (One Pass)

Instead of asking “does some other number pair with this one,” flip the question: as you walk through the array, ask “have I already seen the number that would complete this pair?”

That’s the whole trick. Keep a hash map of value → index as you go. Before inserting the current number, check if target - nums[i] is already in the map. If it is, you’re done. If not, add the current number and move on.

import java.util.HashMap;
import java.util.Map;

class Solution {
    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};
            }
            // check before inserting so we never match an element with itself
            seen.put(nums[i], i);
        }
        return new int[]{};
    }
}

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            # check before inserting so we never match an element with itself
            seen[num] = i
        return []

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> seen;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (seen.count(complement)) {
                return {seen[complement], i};
            }
            // check before inserting so we never match an element with itself
            seen[nums[i]] = i;
        }
        return {};
    }
};

Complexity Analysis:

• Time Complexity: O(n): single pass, O(1) average lookup and insert.
• Space Complexity: O(n): hash map can hold up to n-1 entries before the match is found.

Where it breaks: if the interviewer changes the problem to “return all pairs” instead of “return one pair,” this exact approach needs modification since you’d need to keep scanning instead of returning early. It’s a common follow-up, so it’s worth having an answer ready.

Why Not Sort First?

Sorting and using two pointers is another common answer, and it’s worth knowing why it’s usually not the best choice here: sorting takes O(n log n), and once sorted, you’ve lost the original indices unless you track them separately (usually by sorting an array of (value, originalIndex) pairs). It works, but it adds complexity for no speed benefit over the hash map approach. It’s genuinely useful, though, if the array is already sorted or if you need indices in relative order.

Common Mistakes

• Using the same element twice. If nums = [3,3] and target = 6, you need index 0 and 1, not index 0 twice. The hash map approach handles this naturally because you check the map before inserting the current number.
• Returning values instead of indices. LeetCode wants indices, not the numbers themselves. Easy to mix up under interview pressure.
• Forgetting duplicates can be the answer. Some candidates assume all values are unique and add early-exit logic that breaks on inputs like [3,3].

Frequently Asked Questions

Can you solve Two Sum without extra space? Not in O(n) time. The O(1) space brute-force approach exists but costs you O(n²) time. There’s no known way to get O(n) time and O(1) space simultaneously for the general case.

What if the array is already sorted? Use two pointers, one at each end, moving inward based on whether the current sum is too high or too low. That gets you O(n) time and O(1) extra space, better than the hash map approach when sorting is free.

What does this problem test in interviews? Less about the algorithm itself (most candidates have seen it) and more about whether you can articulate the brute-force-to-optimal trade-off clearly, handle edge cases like duplicates, and respond well when the interviewer changes the follow-up conditions.

← All Problems