Language Selection
Choose your preferred programming language
Two Sum
Problem Statement
You are given an integer array nums and an integer target. Find two different positions in nums whose values sum to target and return those two indices.
Every input is guaranteed to have one and only one valid pair, and a single position cannot be paired with itself.
The two indices may be returned in either order.
Examples
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 6, we return [0, 1].
Constraints
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- Only one valid answer exists.
Approach 1: Hash Map (Optimal)
Algorithm
Use a hash map to store numbers and their indices for O(1) lookup.
Steps:
- Create a hash map to store number -> index mapping
- For each number in the array:
- Calculate complement = target - current number
- If complement exists in hash map, return indices
- Otherwise, store current number and its index in hash map
Implementation
Python:
def twoSum(nums, target):
"""
Find two numbers that add up to target using hash map
Time: O(n)
Space: O(n)
"""
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return [] # No solution found
Java:
import java.util.*;
class Solution {
/**
* Find two numbers that add up to target using hash map
* Time: O(n)
* Space: O(n)
*/
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> numMap = new HashMap<>();
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[]{}; // No solution found
}
}
Go:
func twoSum(nums []int, target int) []int {
/**
* Find two numbers that add up to target using hash map
* Time: O(n)
* Space: O(n)
*/
numMap := make(map[int]int)
for i, num := range nums {
complement := target - num
if idx, exists := numMap[complement]; exists {
return []int{idx, i}
}
numMap[num] = i
}
return []int{} // No solution found
}
JavaScript:
/**
* Find two numbers that add up to target using hash map
* Time: O(n)
* Space: O(n)
*/
function 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 []; // No solution found
}
C#:
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Find two numbers that add up to target using hash map
/// Time: O(n)
/// Space: O(n)
/// </summary>
public int[] TwoSum(int[] nums, int target) {
var numMap = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
int complement = target - nums[i];
if (numMap.ContainsKey(complement)) {
return new int[] { numMap[complement], i };
}
numMap[nums[i]] = i;
}
return new int[] {}; // No solution found
}
}
C++:
#include <unordered_map>
#include <vector>
class Solution {
public:
// Find two numbers that add up to target using hash map
// Time: O(n), Space: O(n)
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<long long, int> numMap; // value -> index
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
// long long avoids overflow: target - nums[i] can reach 2 * 10^9
long long complement = static_cast<long long>(target) - nums[i];
auto it = numMap.find(complement);
if (it != numMap.end()) {
return {it->second, i};
}
numMap[nums[i]] = i;
}
return {}; // No solution found
}
};
Complexity Analysis
- Time Complexity: O(n) - Single pass through array
- Space Complexity: O(n) - Hash map storage
Key Insights
- Hash Map Approach: Most efficient with O(n) time complexity
- Two Pointers (not shown): An alternative is to sort a copy of (value, index) pairs and scan it with two pointers, which takes O(n log n) time
- Complement Strategy: Look for target - current number
- Index Preservation: Sorting loses the original positions, so that alternative must keep each value’s original index alongside it
- Single Pass: Hash map approach processes array only once
Edge Cases
- No Solution: Outside the constraints, since a valid pair is guaranteed; the code returns an empty array only as a defensive fallback
- Duplicate Values: Handle arrays with duplicate numbers
- Negative Numbers: Handle negative numbers correctly
- Zero Target: Handle target sum of zero
- Two Elements: Handle arrays with exactly two elements
Test Cases
def test_twoSum():
# Test case 1: Normal case
nums1 = [2, 7, 11, 15]
target1 = 9
result1 = twoSum(nums1, target1)
expected1 = [0, 1]
assert result1 == expected1
# Test case 2: Different indices
nums2 = [3, 2, 4]
target2 = 6
result2 = twoSum(nums2, target2)
expected2 = [1, 2]
assert result2 == expected2
# Test case 3: Duplicate values
nums3 = [3, 3]
target3 = 6
result3 = twoSum(nums3, target3)
expected3 = [0, 1]
assert result3 == expected3
# Test case 4: Negative numbers
nums4 = [-1, -2, -3, -4, -5]
target4 = -8
result4 = twoSum(nums4, target4)
expected4 = [2, 4]
assert result4 == expected4
print("All tests passed!")
test_twoSum()
Follow-up Questions
- Two Sum II: Handle sorted array?
- Two Sum III: Design data structure for two sum?
- Two Sum IV: Find two sum in BST?
- Two Sum with Constraints: Add additional constraints?
- Two Sum with Duplicates: Handle duplicate values differently?
Common Mistakes
- Same Element Twice: Using same element twice for sum
- Index Order: Returning indices in wrong order
- Hash Map Key: Using wrong key in hash map
- Edge Cases: Not handling no solution case
- Time Complexity: Not optimizing from O(n²) to O(n)
Interview Tips
- Start with Brute Force: Show understanding of the problem
- Optimize with Hash Map: Explain hash map approach
- Handle Edge Cases: Mention duplicate values and no solution
- Discuss Trade-offs: Compare time vs space complexity
- Follow-up Ready: Be prepared for variations and optimizations
Concept Explanations
Two Sum: We need to find two numbers in an array that add up to a target value and return their indices.
Hash Map Approach: We use a hash map to store numbers and their indices. For each number, we calculate its complement (target - current number) and check if it exists in the hash map.
Complement Strategy: Instead of looking for two numbers that sum to target, we look for one number and its complement. This reduces the problem to a single lookup.
Why Hash Map Works: The hash map provides O(1) lookup time, making the overall algorithm O(n) instead of O(n²) brute force.
Space-Time Trade-off: The hash map approach uses O(n) extra space to achieve O(n) time complexity, which is a good trade-off for this problem.
Edge Case Handling: We need to handle cases where no solution exists, duplicate values, and negative numbers correctly.