cf.completefrontend
ARRAYS & HASHING · FOUNDATION

Hash set lookup

Remember the values you've seen in a Set, so checking "have I seen this before?" takes constant time.

Time O(n)Space O(n)13 practice problemsStep-through picture

The idea

A set is a collection that holds each value at most once. A hash set, like JavaScript's Set, can add a value or check whether it holds a value in about the same tiny amount of time whether it holds ten values or ten million.

That makes it the tool for any question shaped like "have I seen this before?" or "is this value allowed?". Without a set, you would scan an array every time, which takes longer as the array grows. With a set, each check is instant.

The code here finds the first value that repeats. It walks the list once, asks the set whether each value was seen before, and adds it if not.

An everyday example

A guest list at the door

A bouncer at a party stamps each guest's hand on the way in. When someone tries to enter, the bouncer only has to look for the stamp: no stamp, let them in and stamp them; a stamp, this person has already been inside. The bouncer never has to look through the whole crowd to answer the question.

How the example maps to the code
In the exampleIn the code
The stamps the bouncer has givenseen, a Set
Looking for a stampseen.has(item)
Stamping a new guestseen.add(item)
Someone who already has a stampreturn item: the first repeat

From the slow way to hash set lookup

  1. The obvious way to find a repeat: for each item, look through all the items before it. Item number i needs i comparisons, so a list of n distinct items costs about n² / 2 comparisons. For 20,000 ids that is 200 million.
  2. Look at what the inner loop asks each time: "is this value among the ones before it?". And the group it asks about only ever grows by one item at a time. So instead of rescanning that group, keep it in a structure that can answer "is this value in here?" quickly.
  3. A sorted array could answer with binary search, but inserting into the middle of it shifts many items. A hash set does better: it turns each value into a hash, a number that says where to store it, so both has and add take about the same short time whatever the set's size.
  4. So walk the list once. Before adding an item, ask the set whether it's already there. The first time the answer is yes, that item is the first repeat, and you can stop. That loop is hash set lookup.

How it works

  1. Create an empty Set called seen.
  2. Walk through items in order.
  3. For each item, ask seen.has(item).
  4. If it's there, this item appeared before: return it.
  5. Otherwise add it with seen.add(item) and move on.
  6. If the walk ends with no repeat, return null.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function firstRepeat(items) {
  2. const seen = new Set();
  3. for (const item of items) {
  4. if (seen.has(item)) {
  5. return item;
  6. }
  7. seen.add(item);
  8. }
  9. return null;
  10. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each item costs one has and at most one add, both constant time on average. In the worst case every item is distinct and all n go into the set.

  • Best caseO(1)

    The second item equals the first, like [4, 4, 9, 2]: one add, one has that says yes, and it returns.

  • Average caseO(n)

    The first repeat sits somewhere inside the list, so the number of steps grows with n, each taking about constant time.

  • Worst caseO(n)

    No item repeats, or the only repeat is the last item, like [1, 2, 3, 4, 1]. Every item is checked and added.

Common mistakes

  • Using array.includes(item) on a growing array instead of a Set. Each check scans the array, making the whole loop O(n^2).
  • Adding the item before checking it, so has always says yes.
  • Expecting a Set to treat two equal-looking objects or arrays as the same value. Store a string key instead.
  • Returning 0 or -1 for "no repeat" when those could be real values in the list. Use null or a separate flag.

When to use it

Look for these clues in a problem:

  • The problem asks whether a list has duplicates, or for the first value that repeats.
  • You need to check membership many times: "is this id in the allowed list?"
  • You need the values two lists share, or the values in one list but not the other.
  • A brute force would call array.includes inside a loop, which is O(n^2).

Check yourself

Answer each one in your head first, then open it.

Why must the code check has before calling add?

If it adds first, has always finds the item it just added, so the very first item would be reported as a repeat.

For [7, 2, 7, 2], what is returned, and how many values end up in seen?

It returns 7 at index 2. Only 7 and 2 were added, so seen holds 2 values and the last item is never read.

Why is array.includes on a growing array slower than a Set?

includes scans the array from the start, so each check costs up to the array's length and the whole loop becomes O(n²). A Set check doesn't depend on its size.

How would you return the value that appears first in the list among those that repeat?

Count every value first with a Map, then walk the list again and return the first value whose count is at least 2. For [5, 8, 3, 9, 3, 5] that is 5, not 3.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 13 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: at the top of each step, seen holds exactly the items before the current one. It starts empty, which is right for the first item. Each step that doesn't return adds the current item, so the rule holds for the next step too.

Because of that rule, seen.has(item) is true exactly when item also appears earlier in the list. The loop moves left to right and returns at the first position where that happens, so it returns the value whose second copy comes earliest. No earlier position had a repeat, or the loop would have returned there.

The loop runs at most n times and then stops. If it reaches the end without returning, no item matched an earlier one, so all items are different and returning null is correct.

Going deeper

3 more ideas

Why the first repeat is found

Before looking at index i, seen holds exactly the values at indexes 0 to i - 1. So seen.has(items[i]) is true exactly when items[i] appeared earlier. The loop goes left to right and stops at the first such index, so it returns the value whose second appearance comes earliest.

What counts as the same value

A Set compares values almost like ===: numbers and strings by value, but objects and arrays by identity. Two different arrays [1, 2] and [1, 2] are two separate members. To treat them as equal, store a key made from them, such as the string "1,2".

Set operations

With sets you can combine lists quickly. The values in both a and b: make a set of b, then keep each value of a that it has. The values in a but not b: keep those it doesn't have. Each check is O(1), so the whole job is O(n + m) instead of O(n * m).

Work it by hand

Every step in a table, with why

Find the first repeated value in six numbers. The value that appears first, 5, is not the answer.

items = [5, 8, 3, 9, 3, 5]

Stepitemseen beforeseen.has(item)What happensWhy
15{}falseseen.add(5)The set starts empty, so nothing can be a repeat yet.
28{5}falseseen.add(8)One has check, no scan. 8 is new.
33{5, 8}falseseen.add(3)3 is new as well. The set grows by one item per step.
49{5, 8, 3}falseseen.add(9)Still no repeat. All four values so far are different.
53{5, 8, 3, 9}trueReturn 3The set already holds 3, so this 3 is a repeat. The loop returns at once.

It returns 3 after 5 checks. 5 appeared first, but its second copy is at index 5, later than the second 3 at index 4. The last item is never looked at.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Hash set lookupO(n)O(n)The default for "have I seen this?" questions on any values, when you must keep the list's order.
Sort, then compare neighborsO(n log n)O(1)Memory is tight and you may reorder the list. Repeats become neighbors, but you find the smallest repeated value, not the first one to repeat.
Boolean array indexed by valueO(n + m)O(m)The values are whole numbers from 0 to a small m, so an array of m + 1 flags is faster than hashing.
Check every earlier itemO(n²)O(1)Only for very short lists, where the set's setup costs more than the scans.

Extra memory: O(n) in the worst case, when seen ends up holding every item. When the repeat comes early, seen stays small.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Hash set lookup and the other approaches, on a scale where each line up is 10 times more steps.
  • Hash set lookup O(n)
  • Sort, then compare neighbors O(n log n)
  • Boolean array indexed by value O(n + m)
  • Check every earlier item O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Hash set lookup101,0001 million
Sort, then compare neighbors339,96620 million
Boolean array indexed by value202,0002 million
Check every earlier item1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty list: items = []
The loop never runs and the function returns null.
No repeats: [3, 1, 2]
All three values go into seen, the loop ends, and it returns null.
null is the repeat: [null, null]
It returns null because null repeats, which looks exactly like "no repeat". If null can be in the list, return the index or an object like { found: true, value } instead.
[0, -0] or [NaN, NaN]
A Set treats 0 and -0 as the same value, and NaN as equal to itself, so both lists report a repeat. Plain === would say NaN never matches.
Text that differs only by case: ["Ana", "ana"]
These are two different strings, so there is no repeat. If they should match, store item.toLowerCase() and check that instead.

Variations and follow-ups

Twists interviewers add

A repeat within k positions

To find two equal values at most k indexes apart, keep only the last k items in the set. After handling index i, delete items[i - k]. The set never holds more than k items, so space drops to O(k).

Remove duplicates, keep order

[...new Set(items)] keeps the first copy of each value in its original order. With a key function, keep a set of keys and filter the items whose key hasn't been seen.

The visited set in a graph search

Breadth-first and depth-first search keep a Set of visited nodes and skip any node already in it. It is the same question, "have I seen this before?", and it stops the search from looping forever on cycles.

Longest run of consecutive numbers

Put every number in a set. Start counting only at numbers whose x - 1 is missing, then count up while x + 1, x + 2, and so on are in the set. Each number is counted once, so it is O(n) without sorting.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from words like "contains duplicate", "seen before", "unique", "visited", or "is this value allowed?". Any repeated membership question is the clue.
  • State the rule as you code: "seen holds everything to the left of the current item." It explains why you check has before add.
  • Test four inputs: an empty list, a list with no repeat, a repeat right away, and a repeat at the very end.
  • A common follow-up is "can you use O(1) extra space?". If the values are 1 to n, use cyclic sort or mark visited slots in the array itself. Otherwise, sort first and compare neighbors, at O(n log n) time.

Where frontend code uses it

The same idea in real UI code
  • Removing duplicates with [...new Set(tags)], for example when merging tag lists from several sources.
  • Tracking visited elements or nodes while walking a graph of components or routes, so nothing is processed twice.
  • Checking whether a tag or attribute is on an allow list in an HTML sanitizer.
  • Keeping the ids of selected rows in a table as a Set, so checking whether a row is selected is instant even with thousands of rows.

Related algorithms