hashing · Problem 1 of 5
Two Sum
Amazon
Google
MetaGiven 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 indices in ascending order.
twoSum([2, 7, 11, 15], 9) -> [0, 1]
The obvious approach compares every pair, which is O(n²). There is an O(n) way.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
5 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| twoSum([2,7,11,15], 9) | pair at the start | [0,1] | — |
| twoSum([3,2,4], 6) | pair in the middle | [1,2] | — |
| twoSum([3,3], 6) | duplicate values | [0,1] | — |
| twoSum([-3,4,3,90], 0) | negative numbers | [0,2] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(n)
One pass over the array, with a hash map holding at most n entries. The brute-force pair comparison is O(n²) time and O(1) space — the map trades space for time.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left