1. Two Sum · DSA Practice · EasyLearnSpace

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one valid pair exists, and you may not use the same element twice. Return the indices in any order.

Example 1

Input: nums = [4,9,1,7], target = 11

Output: [0,3]

Explanation: nums[0] + nums[3] = 4 + 7 = 11

Example 2

Input: nums = [-1,8,3,6], target = 2

Output: [0,2]

Explanation: -1 + 3 = 2

Constraints

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

Hint 1

For each number x, the partner you need is target - x.

Hint 2

A hash map lets you check “have I already seen the partner?” in O(1).

ArrayHash Table

Approach 1: Brute force

Try every pair (i, j) with two loops and return the first pair that sums to target.

⏱ Time O(n²)💾 Space O(1)

Approach 2: One-pass hash map ✅

Walk the array once. Before storing x, look up target - x in the map of values seen so far. If it is there, you have the answer.

⏱ Time O(n)💾 Space O(n)

Reference solution for One-pass hash map (time O(n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}                      # value -> index
        for i, x in enumerate(nums):
            if target - x in seen:     # the partner was seen earlier
                return [seen[target - x], i]
            seen[x] = i
        return []

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]);
            if (j != null) return new int[]{j, i};
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen; // value -> index
        for (int i = 0; i < (int)nums.size(); i++) {
            auto it = seen.find(target - nums[i]);
            if (it != seen.end()) return {it->second, i};
            seen[nums[i]] = i;
        }
        return {};
    }
};

function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    if (seen.has(target - nums[i])) return [seen.get(target - nums[i]), i];
    seen.set(nums[i], i);
  }
  return [];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Arrays, Hashing & Prefix Sums.