Skip to content
LEETFLIX

Two Sum

EasyArrayHashing
Solve on LeetCode

The problem every interview loop opens with. One pass, one hash map, done.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

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

You may assume that each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Constraints

  • —2 <= nums.length <= 10^4
  • —-10^9 <= nums[i] <= 10^9
  • —-10^9 <= target <= 10^9
  • —Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

Examples

Input

nums =
[2, 7, 11, 15]
target =
9

Output

[0, 1]

nums

2
0
7
1
11
2
15
3
i
j

Because nums[0] + nums[1] == 9, we return [0, 1].

02

Solution

2 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

Look up the complement before inserting the current value. One pass, O(n).

Walk the array once. At each element ask the map “is `target − x` already here?”. If yes, the stored index plus the current one is the answer. If not, record x → i and keep going.

Because we check before we insert, the map only ever contains elements strictly to the left of the current index, which is exactly the set of legal partners.

Algorithm

  1. Create an empty map seen from value → index.
  2. For each (i, x) compute need = target − x.
  3. If need is in seen, return [seen[need], i].
  4. Otherwise store seen[x] = i and continue.
Time
O(n)
Space
O(n)

Each element is hashed at most twice (one lookup, one insert).

Solution.py
class Solution:    def twoSum(self, nums: list[int], target: int) -> list[int]:        seen: dict[int, int] = {}  # value -> index        for i, x in enumerate(nums):            need = target - x            if need in seen:                return [seen[need], i]            seen[x] = i        return []  # unreachable: exactly one solution is guaranteed
Watch this run

03

Interactive walkthrough

Playing “One-pass hash map”. Edit the input, hit Run, then scrub.

Loading animation…

Up next

#11Container With Most Water

Medium

Python · Go · Animated

#3Longest Substring Without Repeating Characters

Medium

Python · Go · Animated