Interview preparation
Two Sum
1Problem statement
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice. Return the answer in any order.
2Examples
3Constraints
- 2 ≤ nums.length ≤ 10⁴
- −10⁹ ≤ nums[i], target ≤ 10⁹
- Exactly one valid answer exists.
4Approaches
Approach 1
Brute Force
Check every pair (i, j) with i < j and return the first pair whose sum equals target.
Approach 2
Better: Sort + Two Pointers
Sort (value, index) pairs, then move a left and right pointer inward depending on whether the sum is too small or too large.
Approach 3
Optimal: One-pass Hash Map
For each number, look up complement = target − number in a map of previously seen values. If present, return both indices; otherwise store number → index.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
6Complexity
Time
O(n)
Space
O(n)
7Visual walkthrough
Step through this exact algorithm:
Finds two indexes whose values add up to a target in one pass, storing each value's index in a hash map and looking up the complement (target − value).