Remove duplicates from a Python list while preserving the original order. Compare set+list, dict.fromkeys and O(n²) scans with live timing.
The problem
Return a new list with duplicates removed, keeping the first occurrence of each value in its original position order.
set(nums) alone is not an answer: a set has no order you can rely on.
Examples
Example 1
Input
dedupe([1, 2, 2, 3, 1, 4, 3, 5])
Expected output
[1, 2, 3, 4, 5]
Example 2
Input
dedupe(['b', 'a', 'b', 'c'])
Expected output
['b', 'a', 'c']
+ 3 hidden tests on Submit — empty, all duplicates, no duplicates.
Edge cases to ask about
- Empty list
- All the same value
- Unhashable items (lists inside the list) — ask the interviewer
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 |
|---|---|---|---|
| Check `x not in out` on a list | O(n²) | O(n) | Each membership test scans the output list. |
| Seen-set + output list | O(n) | O(n) | Set membership is O(1) on average; the list keeps the order. |
| bestdict.fromkeys(nums) | O(n) | O(n) | Dicts keep insertion order since Python 3.7, so list(dict.fromkeys(nums)) is the one-liner. |
Walkthrough of the optimal approach (try it yourself first)
Keep two structures: a set for fast "seen?" checks and a list for the answer. For each value, append it only the first time you see it.
The tempting if x not in out works, but in on a list is a linear scan, so the whole thing becomes O(n²) — run the Complexity Lab on both versions and watch the curve bend.
Complexity: O(n) time, O(n) space. One pass over the list; each set lookup and insert is O(1) on average. The set and output list can each hold all n values.
Reveal the reference solution
def dedupe(nums): seen = set() out = [] for x in nums: if x not in seen: seen.add(x) out.append(x) return out
The brute force, for comparison
def dedupe(nums): out = [] for x in nums: if x not in out: # a list scan: O(n) per lookup out.append(x) return out
Follow-ups interviewers ask
- How would you dedupe a list of dicts?
- What if the input is too large for memory?
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Remove Duplicates, Keep Original Order in Python?
The optimal solution runs in O(n) time and O(n) auxiliary space. One pass over the list; each set lookup and insert is O(1) on average. The set and output list can each hold all n values.
What is the brute-force approach, and how do you optimise it?
Check `x not in out` on a list: O(n²) time, O(n) space. Each membership test scans the output list. Seen-set + output list: O(n) time, O(n) space. Set membership is O(1) on average; the list keeps the order. dict.fromkeys(nums): O(n) time, O(n) space. Dicts keep insertion order since Python 3.7, so list(dict.fromkeys(nums)) is the one-liner.
What follow-up questions do interviewers ask about Remove Duplicates, Keep Original Order?
How would you dedupe a list of dicts? What if the input is too large for memory?