Contains Duplicate
Contains Duplicate is an easy Arrays & Hashing problem from the Blind 75. The key pattern is hash set, and a good solution runs in O(n) time.
Problem
Given an integer array, print true when any value occurs more than once; otherwise print false.
Examples
Example 1
Input
[8,3,8,1]Output
trueExample 2
Input
[1,2,3,4]Output
falseExample 3
Input
[0,-1,5,-1]Output
trueApproach
Walk the array once and keep every value you have seen in a set. The first value that is already in the set proves a duplicate.
| Pattern | Hash set |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
Sorting first also works in O(n log n) time with no extra set, which is the usual follow-up.