Leetcode #217. Contains Duplicate — Solution

Google image

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

Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solution

This problem can be approached in many ways.

Let us go one by one —

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 entire array. If that element occurs in the array in other places we return true . 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.