Record

Easy · Arrays & hashing

Two Sum

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Every input has exactly one answer.

nums   = [2, 7, 11, 15]
target = 9

→ [0, 1]
Record your take

3 ways to solve it.

Brute force

1function twoSum(nums, target) {
2 const n = nums.length;
3 for (let i = 0; i < n; i++)
4 for (let j = i + 1; j < n; j++)
5 if (nums[i] + nums[j] === target)
6 return [i, j];
7}
js

Two Sum the honest way: start with brute force

O(n²) time · O(1) space
Ama Boateng0:17

Better

1function twoSum(nums, target) {
2 const s = nums.map((v, i) => [v, i])
3 .sort((a, b) => a[0] - b[0]);
4 let lo = 0, hi = s.length - 1;
5 while (lo < hi) {
6 const sum = s[lo][0] + s[hi][0];
7 if (sum === target)
8 return [s[lo][1], s[hi][1]];
js

Two Sum with sorting and two pointers

O(n log n) time · O(n) space
Daniel Osei0:27

Optimal

1function twoSum(nums, target) {
2 const seen = new Map();
3 for (let i = 0; i < nums.length; i++) {
4 const need = target - nums[i];
5 if (seen.has(need))
6 return [seen.get(need), i];
7 seen.set(nums[i], i);
8 }
js

Two Sum, and why the hash map is obvious in hindsight

O(n) time · O(n) space
Kobby Adjei0:21