Solve Two Sum in one pass with a value→index dictionary in O(n): return the indices of the two numbers that add to the target. Includes brute force.
The problem
Return the indices [i, j] (with i < j) of the two numbers in nums that add up to target. Exactly one answer exists. You may not use the same element twice.
Examples
Example 1
Input
two_sum([2, 7, 11, 15], 9)
Expected output
[0, 1]
Example 2
Input
two_sum([3, 2, 4], 6)
Expected output
[1, 2]
+ 3 hidden tests on Submit — same value twice.
Edge cases to ask about
- Duplicate values
- Negative numbers
- Zeros
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Nested loops | O(n²) | O(1) | Try every pair. |
| bestOne-pass hash map | O(n) | O(n) | Store value → index; for each x check whether target − x is already stored. |
Walkthrough of the optimal approach (try it yourself first)
Store each value's index in a dict as you go. For x at index j, the partner is target - x; if it is already in the dict, you have your answer [index_of[need], j].
Checking before inserting is what stops [3] with target 6 from matching itself, while [3, 3] still works.
Complexity: O(n) time, O(n) space. Single pass with O(1) average dict lookups; the dict can store up to n values.
Reveal the reference solution
def two_sum(nums, target): index_of = {} for j, x in enumerate(nums): need = target - x if need in index_of: return [index_of[need], j] index_of[x] = j return []
The brute force, for comparison
def two_sum(nums, target): for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j] return []
Follow-ups interviewers ask
- The array is sorted — O(1) space with two pointers.
- Return all pairs (question 5).
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Two Sum Using a Dictionary in Python?
The optimal solution runs in O(n) time and O(n) auxiliary space. Single pass with O(1) average dict lookups; the dict can store up to n values.
What is the brute-force approach, and how do you optimise it?
Nested loops: O(n²) time, O(1) space. Try every pair. One-pass hash map: O(n) time, O(n) space. Store value → index; for each x check whether target − x is already stored.
What follow-up questions do interviewers ask about Two Sum Using a Dictionary?
The array is sorted — O(1) space with two pointers. Return all pairs (question 5).