Two Sum

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Examples:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6

Output: [1,2]

Input: nums = [3,3], target = 6

Output: [0,1]

Constraints

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Editorial

Intuition:

The key insight is that for each number nums[i], we need to find if there exists another number nums[j] such that nums[i] + nums[j] = target. Instead of checking every pair (O(n²)), we can use a hash map to store each number's index as we iterate. For the current number, we check if its complement (target - nums[i]) already exists in the map. If found, we return the indices immediately.

Approach:

Initialize an empty hash map to store numbers and their indices.
Iterate through the array with index i and current number num.
Calculate the complement: complement = target - num.
If the complement exists in the hash map, return [map.get(complement), i].
Otherwise, add the current number and its index to the hash map.

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(const vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (numMap.find(complement) != numMap.end()) {
                return {numMap[complement], i};
            }
            numMap[nums[i]] = i;
        }
        return {};
    }
};
import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] {numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }
        return new int[0];
    }
}
class Solution:
    def two_sum(self, nums, target):
        numMap = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in numMap:
                return [numMap[complement], i]
            numMap[num] = i
        return []
class Solution {
    twoSum(nums, target) {
        const numMap = new Map();
        for (let i = 0; i < nums.length; i++) {
            const complement = target - nums[i];
            if (numMap.has(complement)) {
                return [numMap.get(complement), i];
            }
            numMap.set(nums[i], i);
        }
        return [];
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the number of elements in nums. We traverse the array once, and each hash map operation is O(1) on average.

Space Complexity: O(n), as in the worst case we store all n elements in the hash map.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories