Duplicate Badge Scan
EasyArrays & HashingFree
Problem
A building's door reader logs the badge number of every person who enters during a fire drill. Each person should badge in exactly once, so a repeated number means someone tapped twice or a badge was cloned.
Given the list of badge numbers ids, return true if any number appears at least twice, and false if every number is distinct.
Example 1
- Input:
- ids = [3, 8, 1, 8]
- Output:
- true
Badge 8 appears at positions 1 and 3.
Example 2
- Input:
- ids = [5, 2, 9]
- Output:
- false
All three badges are different.
Example 3
- Input:
- ids = []
- Output:
- false
Constraints
- 0 ≤ ids.length ≤ 10^5
- -10^9 ≤ ids[i] ≤ 10^9
Hint
Show the first hint
As you read the badges one by one, what do you need to remember to recognise a repeat?
Walkthrough
How to approach it
01Clarify before coding
- Can the list be empty? Yes; with no badges there is no repeat, so return false.
- Do I need to report which badge repeats? No, only whether one exists, which allows an early exit.
- Can I modify or sort the input? Sorting would work but costs O(n log n); ask whether the caller minds the array being reordered.
02Brute force
Compare every pair (i, j) with i < j and return true if any two values are equal.
Cost: O(n²) time, O(1) space: about 5·10^9 comparisons for n = 10^5, far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.