The Two Sum problem is a popular coding interview question that asks you to find two numbers in an array that add up to a given target value. The problem statement typically provides an integer array nums and an integer target. You need to find two elements in the nums array such that their sum equals target and return their indices as an array.
For example, given an array nums = [2, 7, 11, 15] and a target value target = 9, the function should return [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.
The problem can be solved using various algorithms such as brute force, two-pass hash table, one-pass hash table, or two pointers. The time and space complexity of the algorithm may vary based on the approach used.
| Solution | Implementation | Time | Space |
|---|---|---|---|
| Brute force | Iterate through each element x and find if there is another value that equals target - x. |
O(n2) | O(1) |
| Two-pass hash table | In the first iteration, add each element’s value and its index to a hash table. In the second iteration, check if each element’s complement (target - nums[i]) exists in the hash table. | O(n) | O(n) |
| One-pass hash table | While we iterate and insert elements into the hash table, we also look back to check if the current element’s complement already exists in the hash table. If it exists, we have found a solution and return the indices. | O(n) | O(n) |
| Two pointers | Sort the array and use two pointers to scan through the array from both ends until they meet. | O(nlogn) | O(1) |
The one-pass hash table solution is often preferred as it strikes a good balance between time complexity and space complexity, the logic is also straightforward and easy to understand. As soon as the required complement is found in the hash table, the solution can be returned immediately, making it very efficient for cases where the solution is located early in the array.
Here’s my one-pass hash table solution in different languages:
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
// Check if the complement is already in the hash map
if (map.count(complement) > 0) {
// If yes, return the indices of both elements
return {map[complement], i};
}
// Otherwise, store the current element and its index in the hash map
map[nums[i]] = i;
}
// If no solution is found, return an empty vector
return {};
}func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var numToIndex: [Int: Int] = [:]
for (index, num) in nums.enumerated() {
if let complementIndex = numToIndex[target - num] {
return [complementIndex, index]
}
numToIndex[num] = index
}
return []
}def two_sum(nums, target):
num_to_index = {}
for index, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], index]
num_to_index[num] = index
return []function twoSum(nums, target) {
const numToIndex = {}
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i]
if (complement in numToIndex) {
return [numToIndex[complement], i]
}
numToIndex[nums[i]] = i
}
return []
}