AlgoViz

Back to All Questions
Two Sum
Google
Array
Hash Table

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Solution Walkthrough

The brute-force approach would be to use two nested loops to check every pair of numbers, which would be O(n²). We can do much better using a hash table (or a JavaScript Map).

  1. Create a hash map to store numbers we've seen and their indices.
  2. Iterate through the input array nums.
  3. For each number num, calculate the required complement: complement = target - num.
  4. Check if the complement exists in our hash map.
    • If it does, we have found our pair. Return the index of the complement from the map and the index of the current number.
    • If it doesn't, add the current number num and its index to the hash map.

This approach has a time complexity of O(n) because we iterate through the array once, and each hash map lookup is O(1) on average. The space complexity is O(n) to store the hash map.

1
2
3
4
5
6
7
8
9
10
11
Related Algorithms
Hashing →
Linear Search →