Two Sum Using a Dict Lookup

Medium ⏱ 12 min 55% acceptance ★★★★☆ 4.4

Write a function two_sum(nums, target) that returns the indices of the two numbers in list nums that add up to target, using a single pass with a dict mapping value seen so far to its index (the classic O(n) approach, not the brute-force O(n^2) one).

Examples

Example 1

Input

two_sum([2, 7, 11, 15], 9)

Output

[0, 1]

Explanation

nums[0] + nums[1] = 2 + 7 = 9.

Example 2

Input

two_sum([3, 2, 4], 6)

Output

[1, 2]

Explanation

2 + 4 = 6, at indices 1 and 2.

Constraints

Exactly one valid answer exists.
Do not use the same element twice.

Topics

Dictionarieslookup tableclassic

Companies

GoogleAmazonMeta

Hints

Hint 1

For each index i, check if `target - nums[i]` is already a key in a seen dict.

Hint 2

If not found, record `seen[nums[i]] = i` and continue.

← Compare Two Inventory Snapshots Group Anagrams →

Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.