RTE logo
← Back to DSA map
Arrays & Hashing

Two Sum

Find the indices of two numbers that add up to a target.

Easy

Problem

Given 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.
  • You cannot use the same element twice.
  • Return the answer in any order.

Examples

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
nums[0] + nums[1] = 2 + 7 = 9
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
2 + 4 = 6
Input: nums = [3, 3], target = 6
Output: [0, 1]

Approach

Time O(n)Space O(n)
  1. Walk the array once, keeping a map from each value seen so far to its index.
  2. For each number, compute need = target - num: the partner that would complete the pair.
  3. If need is already in the map, return [map[need], i] - the partner came earlier.
  4. Otherwise store num -> i and move on. Checking before storing is what stops an element pairing with itself.

Brute force: Try every pair using a loop inside a loop. That is n x n steps and no extra memory.

Common mistakes

  • Storing before checking lets a number pair with itself, e.g. [3] with target 6.
  • Testing if (map[need]) fails when the partner is at index 0, because 0 is falsy - compare against undefined.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

2SUM
Solution · JS
Array · i=— target=9
20
71
112
153
current lookup appears here
MAP{ }
Index
—
Num
—
Need
—
Map
0
Found
—
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...