Finding duplicates
The pair-by-pair check on the Counting steps page costs n². Remember what you have already seen in a hash set instead, and each new item needs only one lookup. One pass, n steps. The catch is the memory the set takes.
73952846
Does any value appear twice? This time, remember every value in a hash set as you go.
1function hasDuplicate(a) {2 const seen = new Set();3 for (const x of a) {4 if (seen.has(x)) return true;5 seen.add(x);6 }7 return false;8}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the second item repeats the first |
| average | n | one lookup and one insert per item |
| worst | n | no duplicate: every item is stored |
| space | n | the set can hold every value |
Where it breaks
- Trading memory for time. The set can grow to hold every item. When memory is tight, sorting first and comparing neighbours costs n log n with no set at all.
- Compare the two pages. Pick 16 items: 16 lookups here, against 120 compares for the pair-by-pair check. At a million items it is a million lookups against about 500 billion compares.
- Values a set cannot hash. In Python, lists and dicts cannot go in a set, and in JavaScript two equal-looking objects are different set entries. Turn each item into a hashable key first, such as a tuple or a string.