vizlearn

Two Sum

Interview QuestionsBy Updated

One pass with a dictionary. For each value, ask whether its complement target - value has already been seen; if it has, you have the pair. O(n) time and O(n) space, against O(n²) for the nested loops everyone writes first.

Overview

The problem, and the two versions of it

Given an array of integers and a target, return the indices of two numbers that add to the target.

nums = [2, 7, 11, 15], target = 9  →  [0, 1]

There are two versions, and interviewers use both:

Unsorted input. The hash-map solution, O(n) time and O(n) space.

Sorted input. Two pointers, O(n) time and O(1) space.

Knowing which applies is the first thing to establish, and asking "is the array sorted?" is a legitimate and expected clarifying question.

Lists & arraysCoding problemEasy

Step through it

What to watch

  • The dictionary only holds values already passed.
  • Storing after the check is what stops an element pairing with itself.
  • The answer is found without ever comparing two elements directly.

Say this out loud

"One pass with a dict of value to index. For each number I look up target minus it - if it's there, that's the pair. O(n) time, O(n) space. If the array were sorted I'd use two pointers instead and drop the space to O(1)."

Two Sum

Find two numbers in a list that add to a target. Return their indices.

Run it

All three approaches with their operation counts, then the self-pairing bug demonstrated by moving one line, and finally a size where the quadratic version stops being viable.

1Python
Output
2Python
Output
3Python
Output
4Python
Output

                

                

                    
The brute force, and why to mention it

                    
5Python
Output
O(n²) time, O(1) space. State it, give the complexity, and move on to the improvement — that sequence demonstrates you can see the baseline and improve on it, which is part of what is being assessed.
Do not spend time writing it out unless asked.

                

                

                    
The hash-map solution

                    
6Python
Output
One pass, O(n) time and O(n) space.
The insight worth stating out loud: "for each number, I need to know whether its complement has already appeared" — that is a lookup, and a dictionary makes lookups constant time. The nested loop was re-scanning to answer a question a dictionary answers immediately.
Two details that matter:
Check before inserting. If you store x first and then look for target - x, an input like nums = [3, 5], target = 6 matches 3 against itself and returns [0, 0].
One pass is enough. A two-pass version — build the whole dictionary, then scan — also works and needs the same self-pairing guard. The one-pass version is cleaner and is what interviewers expect.

                

                

                    
Turning a search into a lookup

                    
The nested-loop version asks "does any later element pair with this one?", which is n²/2 comparisons. The insight is to invert it: you know exactly which number you need, so the question becomes "have I already seen target - value?" — and that is a dictionary lookup, not a search.
This is the same move as grouping anagrams by a key. Whenever a problem asks you to find a pair with a known relationship, look for the version where one member is computed rather than searched for.

                

                

                    
The two orderings that matter

                    
Check before you store. Storing first lets an element pair with itself when target is exactly twice it — [3] with target 6 returns (0, 0), which is wrong.
Store value → index, not the reverse. The values are what you look up; the indices are what you return. Duplicates overwrite, which is fine because any one valid pair is usually acceptable — ask, if the question does not say.

                

                

                    
When to use two pointers instead

                    
If the input is already sorted, converging pointers solve it in O(n) time and O(1) space: too small means move the left pointer right, too big means move the right pointer left. That is strictly better on memory.
If it is not sorted, sorting to enable that is O(n log n) — worse than the dictionary, and it destroys the original indices, which the question usually asks for. Say why you are choosing the dictionary; that reasoning is most of the mark.

                

                

                    
Walking through an example

                    
nums = [2, 7, 11, 15], target = 9:
ixNeedIn seen?Action
027Noseen = {2: 0}
172Yes, at index 0Return [0, 1]
Two iterations. Tracing a small example aloud is worth doing in an interview — it catches off-by-one and ordering errors before the interviewer has to point them out.

                

                

                    
Edge cases to raise

                    
CaseBehaviour
No solution existsReturn [] or None — ask which is expected
Duplicate values, e.g. [3, 3] target 6Works: the second 3 finds the first
Same element twice, [3] target 6Must not match — the check-before-insert order handles it
Negative numbersWorks unchanged; the arithmetic does not care
Several valid pairsReturns the first found; ask whether all are wanted
Empty or single-element arrayReturn the empty result
Raising the "same element twice" case unprompted is a good signal, because it is the one the naive ordering gets wrong.

                

                

                    
The sorted variant: two pointers

                    
If the array is sorted, O(1) space is achievable:
7Python
Output
The correctness argument: if the sum is too small, the only way to increase it is to raise the left value; if too large, lower the right one. No pair is ever skipped.
 Hash mapTwo pointers
Requires sorted inputNoYes
TimeO(n)O(n)
SpaceO(n)O(1)
Returns original indicesYesOnly if sorted in place
That last row is a real trap: if you sort an unsorted array to use two pointers, the indices you return refer to the sorted array, not the original. Sorting (value, index) pairs preserves them, and at that point the hash map is simpler.

                

                

                    
The follow-ups interviewers ask

                    
"What if you need all pairs?" Do not return early; collect matches. Watch for duplicates — sort and skip repeated values, or track which indices are used.
"What about three numbers summing to the target?" Three-sum: sort, fix one element with an outer loop, and two-pointer the rest. O(n²). This is the most common follow-up, and being ready for it is worth more than optimising two-sum further.
"What if the array is enormous and does not fit in memory?" Sort externally and use two pointers with streaming reads, or partition by hash across machines.
"Can you do it in O(1) space without sorting?" Not in O(n) time. That trade — O(n) space for O(n) time, or O(1) space for O(n log n) including the sort — is the honest answer, and saying so is better than searching for something that does not exist.
"What if the same number can be used twice?" Then insert before checking, and [3] with target 6 returns [0, 0].

                

                

                    
What the question is testing

                    
Two-sum is almost never about two-sum. It is checking whether you:
Recognise a lookup. Converting a nested scan into a hash-map lookup is the single most common optimisation in practical code, and this is the smallest problem that demonstrates it.
State complexity accurately, including space, without prompting.
Handle the self-pairing case, which is the one real subtlety.
Ask about the input. Sorted? Duplicates? Guaranteed solution? All valid pairs or one?
Communicate while coding rather than silently producing an answer.
The pattern generalises far beyond the interview: any time a loop contains a search, a dictionary built beforehand usually removes it. That is the transferable lesson.

                

                

                    
Recap in one screen

                    
  • Ask whether the array is sorted — it changes the answer.
  • Unsorted: one pass with a dictionary from value to index, O(n) time and O(n) space.
  • Check for the complement before inserting the current value, or an element pairs with itself.
  • Sorted: two pointers from both ends, O(n) time and O(1) space, moving the pointer that corrects the sum.
  • The real lesson is turning a repeated scan into a constant-time lookup; three-sum is the standard follow-up.

                

            


        

    



How the code works
All three approaches with their operation counts, then the self-pairing bug demonstrated by moving one line, and finally a size where the quadratic version stops being viable.
How the code works
  1. if target - v in seen:The complement is computed, not searched for. That single substitution is what removes the inner loop and the O(n²).
  2. seen[v] = i   # after the checkOrder is load-bearing. Storing first lets a value pair with itself when the target is double it, which the [3] case demonstrates.
  3. seen: value -> indexValues are what you look up; indices are what you return. Getting this backwards produces a dictionary you cannot query.
  4. two_pointers(sorted(values), target)O(1) space, and the indices now refer to the sorted copy. That is why sorting is the wrong move when the question asks for original indices.
Change one thing
  • Ask for all pairs rather than the first. Store a list of indices per value, because duplicates currently overwrite.
  • Extend it to 3Sum: fix one element, then two-pointer the rest. O(n²) instead of O(n³), and the standard follow-up.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. The one-pass solution works by:
  2. Why must you check before storing the current value?
  3. When is the two-pointer version preferable to the dictionary?





 Cheat sheet
Two Sum
One pass with a dictionary. For each value, ask whether its complement target - value has already been seen; if it has, you have the pair. O(n) time and O(n) space, against O(n²) for the nested loops everyone writes first.
INTERVIEW · vizlearn.in/interview/two-sum.html
More in Interview
InterviewMaximum subarray sum (Kadane)InterviewRemove duplicates from a sorted array in placeInterviewRotate an array by kInterviewProduct of array except self
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact