MiddleCodeOccasionalNot answered yet
Remove duplicates from a list while preserving order
Given a list with repeated values, return a new list with duplicates removed while keeping the order of first appearance.
Requirements:
- preserve first-seen order
- O(n) time
def dedup(items: list) -> list:
# your code here
# dedup([1, 1, 1, 2, 2, 3, 3, 3, 4]) -> [1, 2, 3, 4]Write the implementation.
The cleanest order-preserving way is list(dict.fromkeys(items)) — dict keys are unique and, since 3.7, keep insertion order. Equivalently, iterate once and append items whose value is not yet in a seen set, giving O(n). Plain set(items) deduplicates but loses order, so it does not satisfy the requirement.
- ✗Using
set(items)and assuming it preserves order - ✗Scanning the result list per element, making it O(n^2)
- ✗Sorting first and claiming the original order is kept
- →Why does
dict.fromkeyspreserve order whilesetdoes not? - →How would you dedup a list of unhashable items like dicts?
