Leetcode #217. Contains Duplicate — Solution

Today we are going to solve Leetcode 217. Contains Duplicate.

Photo by James Harrison on Unsplash

Problem Statement

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.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution

This problem can be approached in many ways.

Naive Solution

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 O(n^2) where n is the length of the array.

Sorting

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 O(nlogn) .

Hashing

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.

sksaikia/LeetCode