Developers

Contains Duplicate

EasyHashing and countingAlso known as LeetCode 217

You get a list of integers. Return true if some value appears at least twice, and false if every value is different.

The list can be long, so a solution that compares every pair of values is too slow.

Examples

Input nums = [1, 2, 3, 1]
Output true
The value 1 appears twice.
Input nums = [1, 2, 3, 4]
Output false
Input nums = [7]
Output false
One value cannot repeat.

Constraints

  • 1 <= nums.length <= 100,000
  • -1,000,000,000 <= nums[i] <= 1,000,000,000

Stuck? Take one hint at a time

Common mistakes
  • Comparing every pair of values with two nested loops, which is too slow for 100,000 numbers.
  • Sorting the original list in place when the caller still needs its order.
  • Comparing the set size with the list length, which is correct but never stops early.
Questions an interviewer may ask next
  • Return the first value that repeats, not just whether one exists.
  • Allow the duplicates to be at most k positions apart. (A set of the last k values.)
  • Allow the values to differ by at most t as well. (Buckets of width t + 1.)
  • The list does not fit in memory. What can you do with a hash set, with sorting, with a Bloom filter?