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

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.

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.

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.

Run it in Python

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.

two_sum.pyPython 3
Output
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