Jump to section
Two Sum asks you to find the positions of two numbers in an array that add up to a target. The optimal solution makes one pass with a hash map: for each number, check whether its complement (target minus the number) has already been seen. It runs in O(n) time and O(n) extra space.
The Two Sum Problem
You are given a list of integers and a target integer. Return the indexes of the two different elements whose values add up to the target. You may assume exactly one valid pair exists, and you cannot use the same element twice. The order of the two indexes usually does not matter, but returning them in the order you found them is the common convention.
Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Why: 2 + 7 = 9, and those values sit at indexes 0 and 1.
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Why: 2 + 4 = 6. Note that 3 + 3 would also be 6, but there is only one 3, and an element cannot be paired with itself.
Assumptions to confirm
- Can values be negative or zero? (Assume yes; the hash map approach handles both.)
- Is the array sorted? (Assume no. If it is, there is a two-pointer answer with O(1) space.)
- What if no pair exists? (The classic version guarantees one; returning an empty list is a sensible fallback.)
- Can there be duplicates, such as [3, 3] with target 6? (Yes, and your answer should return [0, 1].)
Asking these takes thirty seconds and shows the interviewer you think about inputs before you write code.
Start With the Brute Force
The simplest correct answer checks every pair: for each index i, loop over every later index j and test whether nums[i] + nums[j] equals the target. It is O(n²) time and O(1) extra space.
Interviewers expect you to say this out loud before optimising. It proves you understand the problem, gives you a fallback if you get stuck, and sets up the real question: where is the repeated work? Here, for every number you scan the rest of the array looking for one specific value, its complement. Looking up one value is exactly what a hash map does in constant time.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
The Optimal Approach: One Pass With a Hash Map
Create an empty map from value to index
It records every number you have already walked past, and where it was.
Walk the array once
For each index i, compute need = target - nums[i]. This is the only value that could complete a pair with the current number.
Check the map before inserting
If need is already in the map, return [map[need], i]. Checking before inserting is what stops an element pairing with itself.
Otherwise store the current number
Save nums[i] with index i, then move on. A later number may need it.
Fall back if no pair is found
With the classic guarantee this never runs, but returning an empty list keeps the function total.
Two Sum Solution in Python and TypeScript
Both versions follow the steps above exactly. The comments mark the two lines interviewers most often ask about.
Python
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {} # value -> index
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []TypeScript
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>(); // value -> index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
const j = seen.get(need);
if (j !== undefined) return [j, i];
seen.set(nums[i], i);
}
return [];
}Why does storing after checking matter? With nums = [3, 3] and target 6, the first 3 is checked against an empty map, then stored. The second 3 finds the first one, so the answer is [0, 1]. If you stored first, a single 3 with target 6 would wrongly match itself.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Time and Space Complexity
| Approach | Time | Space | When to use it |
|---|---|---|---|
| Brute force (all pairs) | O(n²) | O(1) | Tiny inputs, or as your first spoken answer |
| Sort + two pointers | O(n log n) | O(n) to keep original indexes | Input already sorted, or memory is tight |
| One-pass hash map | O(n) | O(n) | The expected interview answer |
How to Talk Through Two Sum in an Interview
A strong spoken answer follows the same five beats every time:
- Clarify: "Can there be negative numbers or duplicates? Is exactly one answer guaranteed? Do you want indexes or values?"
- Brute force: "The direct way is to try every pair, which is quadratic. That works but repeats the same search for each number."
- Optimise: "For each number I only need one specific partner, target minus the number. If I keep everything I have seen in a hash map, I can check for that partner in constant time, so the whole thing is one pass."
- Code: narrate as you type, especially the check-before-insert line and why it prevents self-pairing.
- Test: walk through [2, 7, 11, 15] with target 9, then the [3, 3] case, then a case with no answer. State the complexity: O(n) time, O(n) space.
Saying the trade-off out loud (more memory for less time) is often what separates a pass from a strong pass on an easy problem.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Edge Cases and Common Follow-Ups
Duplicates such as [3, 3]
Handled by checking the map before inserting the current value.
Sorted input
Expect "can you do it in O(1) space?" Use two pointers from both ends: move the left pointer up if the sum is too small, the right pointer down if too large.
Return all pairs, not one
Keep counts in the map and collect every match, taking care not to report the same pair twice.
Three numbers instead of two
That is Three Sum: sort, fix one number, then run two pointers on the rest for O(n²).
A data stream
Design a class with add(number) and find(target). Discuss which operation you make fast, since you cannot make both O(1).
Practise Two Sum in a Mock Coding Round
Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Two Sum out loud, under time pressure, while explaining each decision.
MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).
Frequently Asked Questions
How do you solve Two Sum in O(n) time?
Is Two Sum an easy interview question?
Can Two Sum be solved without extra space?
Why check the map before adding the current number?
What should I say about complexity?
Stop Preparing in Your Head. Start Practicing Out Loud.
Drop your resume, add a job description, and get a mock interview like the real thing.
Start Free Mock Interview →Still applying for jobs? Let Auto Apply do it for you.