Part 2 · Problems · Arrays and hashing
Two Sum
#1 · Easy · LeetCode
Given an array of numbers and a target, return the indexes of the two numbers that add up to the target. Exactly one answer exists. You can't use the same element twice.
nums = [2,7,11,15], target = 9 -> [0,1] nums = [3,3], target = 6 -> [0,1]
Ask before coding
- Can there be negative numbers?
- Always exactly one answer?
- Return indexes or values?
Hint
For each number, the partner you need is target - num. Have you seen it already?
Approach
Walk once. Keep a Map of value to index for everything seen so far. For each number, check if target - num is in the map. Check before inserting, so a number never pairs with itself.
Time O(n) Space O(n)
Watch it run
Solution (JavaScript, tested)
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i);
}
return [];
}Traps
- Inserting before checking pairs a number with itself (fails [3,3] target 6 the other way round).
- The brute force double loop is O(n²). Mention it, then improve.
Say out loud: Brute force is two loops, O(n squared). I can trade memory for time: store what I've seen in a map, then each lookup is O(1).