Two Sum in O(n) Time
easyArrays & Objects+150 XPFrontend AlgoArena
The classic warm-up: given an array of integers nums and a target sum, return the indices of the two entries that add up to it.
The nested-loop solution is O(n²). The one every interviewer is actually looking for uses a hash map to turn the second lookup into O(1), so the whole thing runs in a single pass.
Arguments
numsnumber[]- The input array of integers.
targetnumber- The sum you are searching for.
Returns
number[] — A two-element array [i, j] with the indices whose values sum to target. Returns [] when no such pair exists.
Examples
twoSum([2, 7, 11, 15], 9);
// [0, 1] — nums[0] + nums[1] === 9
twoSum([3, 2, 4], 6);
// [1, 2]twoSum([1, 2, 3], 10);
// [] — no pair sums to 10What it has to do
- Return indices as an array
[i, j]. - Must run in O(n) time using a Map / Hash Object.
- Return empty array if no pair exists.
Notes
- Record each value's index _after_ checking the map, so a single element isn't matched with itself.
Try it yourself· Edit the code, then press Run
Loading playground...
- 1.finds indices summing to target
- 2.handles non-adjacent indices
These assertions run in your browser the moment you hit Run. Pass all of them to claim the XP.
2 tests · +150 XP
Discussion
Sign in to postSign in to join the conversation.Sign in
No comments yet. Be the first to say something.