Two Sum with Dict

Find two numbers in a list that add up to a target using a dictionary for O(n) speed.

dictionary pair-sum hash-map

Write a function `two_sum(nums, target)` that takes a list of integers `nums` and an integer `target`. It must return a list `[i, j]` of the indices of two distinct numbers in `nums` such that `nums[i] + nums[j] == target`. You may assume exactly one valid pair exists. The solution must use a dictionary (hash map) to achieve O(n) time. The order of indices in the returned list does not matter.

Constraints

- `2 <= len(nums) <= 10^5`
- Each `nums[i]` is an integer (may be negative or zero).
- Exactly one valid pair exists.
- Time complexity O(n), space O(n).

Example

>>> two_sum([2, 7, 11, 15], 9)
[0, 1]
>>> two_sum([3, 2, 4], 6)
[1, 2]
>>> two_sum([3, 3], 6)
[0, 1]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about what value you need to look up in the dict for each number.

Store each number along with its index as you iterate.

Check if the complement (target - current) is already in the dict before adding the current number.

Since exactly one pair exists, you don't need to worry about multiple matches.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.