Where it runs
1. The problem
In the Big-O lesson you learned to spot the O(n2) trap: a loop inside a loop over the same list. It often hides in the question "does this list have a repeat?" If you compare every item with every other item, a list of a million items costs about a million times a million comparisons.
There is a tool that answers "have I seen this value before?" in about one step, however long the list is. It is called a Set. With it, the same question takes one walk over the list. This lesson opens a small group of such built-in tools.
2. In plain words
A Set is a bag of values with one rule: it never holds the same value twice. Take the list ["a", "b", "a", "c"] and drop its values into an empty bag one by one. "a" goes in. "b" goes in. The second "a" changes nothing, because "a" is already inside. "c" goes in. The bag now holds "a", "b" and "c", one of each.
The bag can also answer a question: "is "b" inside?" The answer, yes or no, comes at once. Nobody has to tip the bag out and look through it.
So the bag keeps one copy of each value and tells you right away whether a value is inside.
3. The idea
JavaScript has this bag built in. It is called a Set: a collection that holds each value at most once.
You do three things with it:
bag.add(x): putxin. Ifxis already in the bag, nothing changes.bag.has(x): ask whetherxis in the bag. The answer,trueorfalse, comes in about one step.bag.delete(x): takexout.
And bag.size tells you how many different values the bag holds right now.
People use a Set for that "about one step". A plain array can also tell you whether it holds a value, but it walks the whole array to find out: indexOf and includes are O(n). A Set is built so that the time of has does not depend on how many values it holds. You will see how a few lessons from now, in the lessons on hashing. For now, take it on trust that has, add and delete each take about one step.
To get every different value in the order you first met it, walk the list once. For each value, check the Set. If the value is not there, add it to the Set and keep it in the answer. If it is already there, skip it. Trace ["a", "b", "a", "c"]: a is new, keep it; b is new, keep it; a is already in the Set, skip it; c is new, keep it. Result: ["a", "b", "c"].
To answer only "is there any repeat?", walk the list too. The first time has says yes, stop and return true. On ["a", "b", "a"] that happens at the third item. If you reach the end and has never said yes, there was no repeat.
4. What it costs
Each has, add and delete costs about O(1): one step, however many values the Set holds. Reading size is O(1) too.
Removing repeats from a list of n values costs O(n) time. That is one walk, with one has and maybe one add per value. Memory is O(n) in the worst case, when every value is different and they all go into the Set. That extra memory is the price: one walk replaces the O(n2) loop inside a loop.
Checking for a repeat also costs O(n) time and O(n) memory in the worst case. It can stop early, though. The moment it meets a value it has seen before, the function returns the answer and never reads the rest of the list.
5. Where this shows up
A program removes repeats from a stream of visitor IDs or tags, then counts "unique visitors" or "different tags". It guards against handling the same request twice: it keeps a Set of the request IDs it has already handled and drops any ID it has seen before. A crawler (a program that walks through websites and downloads pages) remembers the pages it has already downloaded, so it never goes round in circles. A form stops you from entering the same thing twice, for example the same email recipient. Whenever the question is just "is this already in the collection?", reach for a Set first. The answer stays cheap however big the collection grows.
On LeetCode
Problems that ask whether a value was seen before, whether a list has a repeat, or which values two lists share. A Set answers each of these questions in about one step.
This is hasDuplicate from the lesson, returning true the moment has says yes.
Put the first array in a Set, then collect the values of the second that it has, each one once.
Put the jewel letters in a Set and count the stones it has.
With all numbers in a Set, start counting at x only when the Set has no x minus 1.
Your task (Tier 1)
Write two functions: dedupe(items) and hasDuplicate(items).
Both use a set: a bag that holds each value only once. Use it as a memory of "have I seen this already?".
- Input:
items, a list of values (text or numbers). Example:["a", "b", "a"]. dedupereturns a new list that keeps each value once, in the order it first appeared.hasDuplicatereturnstrueif any value appears more than once, andfalseotherwise.
Steps:
- Make an empty set
seen. - For
dedupe: go through the list. When a value is not inseen, add it toseenand add it to the answer list. Return the answer list. - For
hasDuplicate: go through the list. When a value is already inseen, returntrue. Otherwise add it toseen. If you reach the end, returnfalse.
Done when all tests pass:
dedupe:
["a","b","a","c","b"]->["a","b","c"]["a","b","c"]->["a","b","c"](all different, nothing removed)["z","z","z"]->["z"](all the same, one kept)["x", 7, "x", 7, "y"]->["x", 7, "y"](a list with both text and numbers)[]->[](empty list, must not crash)
hasDuplicate:
["a","b","a"]->true("a"repeats)[1, 2, 3]->false(all different)["z","z","z"]->true["x", 7, "y"]->false[]->false(empty list)
Practice
dedupe / hasDuplicate
export function dedupe(items) {
// Your code here. The task is described in the box above the editor.
}
export function hasDuplicate(items) {
// 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.