13Two Sum using a hash map
easyAbout 15 minutesCodinghash-maparrays
Problem
Implement twoSum(nums, target). Return the indexes [i, j] of two different elements whose sum is target, with i < j. If no pair exists, return [].
twoSum([2, 7, 11, 15], 9); // [0, 1]
twoSum([3, 2, 4], 6); // [1, 2]
twoSum([3, 3], 6); // [0, 1]Requirements
- Do not use the same element twice.
- Solve it in O(n) time with a hash map.
- When several pairs exist, return the first pair completed while scanning from left to right.
Try it yourself
Write your solution, run it, then submit to check it against the tests.
solution.jsJavaScript
Press Run or ⌘ Enter to execute your code.
Video walkthrough
Stuck? Watch someone solve it, then try again on your own.
Step-by-step
Checking every pair with two loops is O(n²). Say it out loud, then improve it: for each number you only need to know whether its complement, target - num, appeared earlier.
Unlock the full solution
What's inside
- Step-by-step
- Approach
- Solution
- Complexity
- Edge cases
- Follow-up questions
- Tests
Includes 2 code listings, 4 edge cases, 4 follow-up questions.
One-time payment by UPI, card or net banking. Launch price.