DSA Factory
Free lessonsHashing · Stage 0 · Seen before? · Step 1

A set remembers

Spot a repeated value in one pass by remembering what you've seen. About 7 minutes.

Comparing every pair is slow

Does a list contain the same value twice? The obvious way is to compare each value with every value after it. That's fine for 100 values. For a million, it's about 500 billion comparisons, far too slow.

The trouble is that each new value makes you look back through everything you've seen. What if you could remember what you've seen in a way that answers "have I seen this before?" instantly?

Every pair: about n × n steps: hopeless for big lists.
Walk once, remember as you go
4
0
2
1
7
2
2
3
9
4
i

4 isn't in {}. Add it: seen = {4}.

Move 1 of 4

A set remembers what you've seen

A set is exactly that memory. Walk the list once. For each value, ask the set whether it's already there. If it is, you've found a repeat. If not, add it and move on.

Each question takes about one step, so the whole walk takes about n steps instead of n × n. Every language has one: a set in Python, an unordered_set in C++, a HashSet in Java, a Set in JavaScript.

Is it in the set? about one step, however big the set.
In code
seen = set()
for x in nums:
    if x in seen:
        return True
    seen.add(x)
return False
Quick check

You walk 5, 1, 5 with an empty set. When do you first find a repeat?

  1. AAt the second 5 (box 2)
  2. BAt the first 5 (box 0)
  3. CNever
Show the answer

At the second 5 (box 2). The first 5 and the 1 are added first. The second 5 is found in the set.

Your problem

Any repeats?

Return true if some value appears more than once in nums, and false if every value is different.

Example
nums = [4, 2, 7, 2, 9] → true

0 ≤ n ≤ 1,000,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding