AlgoViz
HomeArrays & Hashing

Two Sum

Easy

Unsorted input · remember complements in a map

In simple words

For each number, remember it; when a later number is the exact partner you need, you've found the pair.

The idea

For each number, the partner you need is target − num. Store every number you pass in a map; when the partner shows up, you're done — in a single pass.

3
2
4
0
1
2
target6

Step 1 of 4. Brute force: test every pair and check if it adds to 6. Values: 3, 2, 4. target 6.

1/4
Brute force
timeO(n²)spaceO(1)

Check every pair.

1// try every pair2for (let i = 0; i < n; i++)3  for (let j = i + 1; j < n; j++)4    if (nums[i] + nums[j] === target)5      return [i, j];6return [-1, -1];

Input

array
[3, 2, 4]

Memory

i
—
j
—
target
6
pairs tried
—
sum
—

Output

sum
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [2, 7, 11, 15], target = 9
Output:
[0, 1]
Explanation:
nums[0] + nums[1] = 2 + 7 = 9.

Example 2

Input:
nums = [3, 2, 4], target = 6
Output:
[1, 2]
Explanation:
nums[1] + nums[2] = 2 + 4 = 6.

Example 3

Input:
nums = [3, 3], target = 6
Output:
[0, 1]
Explanation:
The two 3s add up to 6.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.