Two Sum
EasyProblem Description
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.
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]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
Solution Approaches
Step 1: Brute-Force Approach
The most straightforward solution is to use nested loops. For each element x in the array, we iterate through the rest of the array to find an element y such that x + y = target.
Intuition:
- Check every possible pair of numbers - If we find a pair that sums to the target, return their indices - This approach is simple but inefficient for large arraysAlgorithm:
1. Loop through each element x at index i
2. For each x, loop through elements after it at index j
3. Check if nums[i] + nums[j] === target
4. If yes, return [i, j]
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return []; // Should never reach here per problem constraints
}Starting brute-force search for two numbers that sum to 9. We'll check every possible pair of numbers.
Step 2: Optimized Approach with a Hash Map
A better approach uses a hash map (object/Map) to store numbers we've seen and their indices. For each element, we check if its complement (target - element) already exists in the map.
Intuition:
- Instead of checking all pairs, we look up the complement in constant time - We trade space for time: use extra memory to achieve better performance - As we iterate, we build up our "seen" mapAlgorithm:
1. Create an empty hash map to store {number: index}
2. Loop through each element at index i
3. Calculate complement = target - nums[i]
4. If complement exists in map, return [map.get(complement), i]
5. Otherwise, store nums[i] in map with its index
6. Continue to next element
Key Insight: By the time we reach a number, its complement (if it exists) would already be in our map from previous iterations.
function twoSum(nums: number[], target: number): number[] {
const map = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement)!, i];
}
map.set(nums[i], i);
}
return []; // Should never reach here per problem constraints
}Starting optimized hash map approach. We'll use a hash map to store seen numbers and their indices. This allows us to find the complement in O(1) time instead of checking every pair.