Solution: Contains Duplicate

Statement#

For a given array of integers, nums, return TRUE if it contains duplicates. Otherwise, return FALSE.

Constraints:

• $1 \leq$ nums.length $\leq 10^5$

• $-10^9 \leq$ nums[i] $\leq 10^9$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time and any implementation constraints.

Naive approach#

The first solution that comes to mind while looking at this problem would be to iterate over all the elements of the nums array and compare each element with $(i-1)$ elements to check whether it is repeating. In this way, we will be able to find out if there are repeating duplicate numbers in the array. However, it is an expensive solution in terms of time complexity, since it comes out to be $O(n^2)$.

This can be improved in terms of time complexity. Let’s try to devise an optimized solution.

Optimized approach using knowing what to track#

An efficient approach would be to keep track of numbers while iterating over nums. This way, we can find out if an element is repeating by just checking its occurrence instead of checking all the rest of the numbers in nums.

To achieve this, we will be using the hash map data structure records that is appropriate for problems like this. We iterate over the nums array, and for each number, we check if it exists in records or not. If it exists, then it means that the number is being repeated and the given array nums contains duplicates hence we return TRUE. If it is not the case, we add the current number to the records and move to the next number.

If all the numbers have been processed and we haven’t encountered any duplicates, we return FALSE, meaning that there is no duplicate in the given nums array.

Let’s look at the illustration below to better understand the solution.

Solution Summary#

To recap, the solution to this problem can be divided into the following parts:

1. Initialize hash map records to store the numbers which were iterated.
2. We iterate over nums and check for each number if they are being repeated or not, by checking records.
3. If it exist, then return TRUE otherwise, return FALSE.

Time complexity#

The time complexity of this solution is $O(n)$. The average case of inserting and searching operations takes $O(1)$ time. However, in the worst case where hash collisions occur, time complexity goes up to $O(n)$, hence the total time complexity, in the worst case, is $O(n^2)$.

Space Complexity#

The space complexity would be $O(n)$ to maintain the hash map.