Today we are going to solve Leetcode 217. Contains Duplicate.
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
This problem can be approached in many ways.
In the naive approach, we will check whether a number is repeated or not. For that, we will choose one number and will search for it in the array. If that element occurs in the array in other places we return
true . In the end, if we have not found any repetitions, we can return
false . This will give us a Time Complexity of
n is the length of the array.
We can also use sorting to solve this problem. At first, we will sort the array, and then check if any adjacent elements are equal, if it is equal we can return
true . This approach is better than the previous one, for sorting we require
O(nlogn) time and for searching adjacent elements, we require
O(n) time. Therefore the overall Time Complexity will be
Whenever there is a problem associated with occurrence, duplication and frequency we may be able to apply hashing to solve that problem. In this case, we are going to use
HashSet to solve the problem. We will store each element of the array in an
HashSet and if there is an occurrence, we can return
true . If we do not find any repetitions, we can return false.
The time complexity for this approach is
O(n) and space complexity is
O(n) , because we are using extra space for the HashSet.
All the codes can be found here.