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)

Walk the array once, keeping a map from each value seen so far to its index.
For each number, compute need = target - num: the partner that would complete the pair.
If need is already in the map, return [map[need], i] - the partner came earlier.
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

Speed1×

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.

LanguageEdit and run it here

JavaScript solution

Loading...

Output

Run code to see output...