Double-Scanned Tickets

Easyhash mapAlso known as Contains Duplicate

You run the door at a small concert. Every ticket has a printed code, and the scanner writes each code it reads into a log, in the order people walk in.

Each ticket is good for one entry. If the same code shows up twice, someone copied a ticket. After the doors close, you want to know: did that happen tonight?

Your task

Write hasRepeat(codes). Return true if any code appears in the log two or more times, and false if every code is different.

An empty log has no repeats, so return false.

hasRepeat(codes: int[]) → bool

Examples

Example 1

Input

codes = [4021, 7788, 1290, 7788, 5003]

Output

true

Why

Code 7788 was scanned at positions 1 and 3. One repeat is enough, so the answer is true.

Example 2

Input

codes = [310, 52, 9001, 47]

Output

false

Why

Four scans, four different codes. Nobody got in twice.

Example 3

Input

codes = [88, 15, 42, 88]

Output

true

Why

The repeat does not have to be next to the first scan. Here the copied ticket came in last, three people after the original.

Constraints

0 ≤ codes.length ≤ 100,000
0 ≤ codes[i] ≤ 1,000,000,000

Start with brute force

Compare every scan with every later scan, and return true as soon as two match.

That is about n²/2 comparisons. With 100,000 scans it is around 5 billion checks, far too many. Sorting first and comparing neighbours is faster, O(n log n), but it still does more work than needed and reorders the log.

Hints

0 of 4 shown

Hint 1
Look at the first example. When the scanner reads the second 7788, what would it need to remember from earlier to raise the alarm?
Hint 2
You only need one fact about each earlier code: has it been seen already? You do not care where or how many times.
Hint 3
Which structure answers "is this value already in my collection?" in one step, without scanning everything you stored?
Hint 4
Walk the log once with an empty set. For each code, if it is already in the set, return true right away. Otherwise add it. If you reach the end, return false.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The brute force asks every new scan to search the whole log again. Instead, keep a set of the codes you have already let in, so the check is one lookup.

Trace [4021, 7788, 1290, 7788, 5003]:

4021: the set is empty, so it is new. Set: {4021}.
7788: not in the set. Set: {4021, 7788}.
1290: not in the set. Set: {4021, 7788, 1290}.
7788: already in the set. Return true. The last scan, 5003, is never looked at.

Stopping early matters in practice: if the copy comes in near the start, you are done almost at once.

Reference solution

function hasRepeat(codes) {
  const seen = new Set();
  for (const code of codes) {
    if (seen.has(code)) return true; // scanned before
    seen.add(code);
  }
  return false;
}

def has_repeat(codes):
    seen = set()
    for code in codes:
        if code in seen:  # scanned before
            return True
        seen.add(code)
    return False

TimeO(n)One pass, and each set lookup or insert is O(1) on average.

SpaceO(n)With no repeats, the set ends up holding every code.

Learn the idea: Hash Tables Arrays

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code