Where it runs
1. The problem
You have a list of user IDs, and you want to know whether any ID appears twice. The first idea is to take each ID and compare it with every other one. For a short list that is fine. For a million IDs it is a million times a million comparisons: the O(n2) trap from the Big-O lesson.
There is a move that answers "have I seen this before?" in about one step, however long the list is. It needs extra memory. That exchange of memory for speed is what this lesson is about.
2. In plain words
Take the test list of ids a, b, a. Comparing every pair means checking a against b, a against a, and b against a. With three ids that is 3 comparisons. With a million ids it is about 500 billion.
Instead, keep a record as you walk. Read a: the record is empty, so write a down. Read b: not in the record, write it down. Read a: it is already in the record, so a is a repeat. Each question took one look at the record, and the list was read once.
Sometimes "seen it" is enough, as here. Sometimes you need to know how many times each value came up, and then the record keeps a count next to each value. For the event types x, x, y the record ends as x: 2, y: 1. Either way, one quick look at the record answers the question, however long the list is.
3. The idea
You need two tools, and both are built into JavaScript.
A Set is a bag of unique values (each one is in it once). You can ask seen.has(x), meaning "is x already in the bag?", and the answer comes in about one step. You walk the list once. Before you use a value, you check the bag. If the value is there, you have found a repeat. If not, you put it into the bag with seen.add(x).
A Map is a set of key → value pairs. It is handy for counting: for each item, you write its count as "the old value plus one". A key that is not there yet counts as zero. So counts.get(k) ?? 0 gives the current count. The sign ?? means "if the left side is nothing, take the right side".
Trace a count on ["a", "b", "a"]. See a: there is no count for a yet, that is 0, plus one, which gives {a:1}. See b: that gives {a:1, b:1}. See a again: it was 1, now 2, which gives {a:2, b:1}. Now a repeat check on [3, 1, 3]. See 3: not in the bag, put it in. See 1: not there, put it in. See 3: it is already in the bag, a repeat is found. Each task needs one pass.
4. What it costs
Time is O(n): one pass, and each check or update takes about one step. Memory is O(n): in the worst case every value is different, and all of them go into the structure. That memory is the price. You pay O(n) extra memory and get one O(n) pass instead of an O(n2) nested pass. The in-place array lesson went the other way: there you kept extra memory down to O(1). When the list is big, paying memory for speed is usually worth it.
Use a Map instead of a plain object in three cases: the keys are numbers, the order of adding matters, or a key might match a built-in name like "constructor".
5. Where this shows up
Idempotency and replay detection: has this request or message ID been handled already? If so, it is not run a second time. Metrics rollups per endpoint (the address requests come to) or per status code. Removing repeated events from a stream. Counting unique users. When records from a stream are summed up by key, a Map is the first choice. For the check "seen this one already", a Set is the first choice. You will use both all the time in this course.
firstDuplicate([3, 8, 1, 5, 8, 3])Find the first number that appears a second time. A Set remembers every number met so far and answers 'have I seen this?' in one step.
Bars: the numbers. Only the last one repeats an earlier one.
One operation is one comparison, or one lookup or insert in the hash set. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n²)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- have I seen this before
- count how many of each
- find duplicates
- does a matching/complement value exist
- data is in any order / unsorted
Looks similar, isn't
- Two pointers (opposite ends)
Two pointers need a sorted array and use no extra memory. Hashing is the answer when sorting is off the table.
- Sliding window (variable)
A window answers a question about one contiguous span. A plain map has no idea of a span.
- Non-comparison sort (counting / radix)
Counting sort also tallies frequencies, but it needs small integer keys. A map takes any key at all.
- Trie (prefix tree)
A trie shares prefixes between keys, so it can answer prefix queries. A map only matches whole keys.
- Prefix sums
Prefix sums answer range questions over values kept in order. A hash keeps no order.
n up to 1e6 unsorted values gives O(n) time. Space is O(n), because every distinct key is stored.
On LeetCode
Problems that ask whether you have seen a value before, or how many times each value appears. One pass with a Set or a counting Map replaces the loop inside a loop.
Store each number with its index, and before storing it look up target minus the number.
Count the letters of one word, subtract the letters of the other, and every count must end at 0.
Count every letter first, then scan again for the first letter with a count of 1.
Keep a count of the numbers still waiting for a pair, and match each new number with a waiting k minus number.
Your task (Tier 1)
Write two functions: countEventTypes(records) and findDuplicateIds(records).
Pick the tool from the question. Counting how many times something appears means a Map. Checking whether something appeared before means a Set.
- Input:
records, a list of items, each with atypeand anid. countEventTypesreturns a map from eachtypeto how many times it appears.findDuplicateIdsreturns the list ofids that appear more than once, each listed once.
Steps:
- For
countEventTypes: make an empty mapcounts. For each record, add 1 to the count under itstype(start from 0 the first time). Returncounts. - For
findDuplicateIds: make an empty setseenand an empty result list. For each record, if itsidis already inseen, it is a repeat: add it to the result, but only if it is not in the result yet. Otherwise put theidintoseen. Return the result. Without that check, the test[a, a, a]would give["a", "a"]instead of["a"].
Done when all tests pass:
countEventTypes:
[{id:"a",type:"x"}, {id:"b",type:"x"}, {id:"a",type:"y"}]->x: 2,y: 1[{id:"a",type:"x"}, {id:"b",type:"y"}, {id:"c",type:"z"}]->x: 1,y: 1,z: 1[]-> empty map
findDuplicateIds:
[{id:"a"}, {id:"b"}, {id:"a"}]->["a"][{id:"a"}, {id:"b"}, {id:"c"}]->[](all ids different)[{id:"a"}, {id:"a"}, {id:"a"}]->["a"](a repeated id is listed once)[]->[]
Practice
countEventTypes / findDuplicateIds
export function countEventTypes(records) {
// Your code here. The task is described in the box above the editor.
}
export function findDuplicateIds(records) {
// Your code here. The task is described in the box above the editor.
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.