LeetCode - Contains Duplicate Fastest Solution

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no.217 Contains Duplicate. This question also features in GeeksForGeeks problem set, Check if array contains duplicates.

Problem Statement: Contains Duplicate

Given an array of integers nums, write an algorithm that returns true if any value appears at least twice in the array, and return false if every element is unique.

Example 1:

Input: nums= [1, 2, 3, 4]
Output: false  
Explanation: There are no duplicates in the given array.

Example 2:

Input: nums= [1, 2, 3, 1]
Output: true  
Explanation: The given array contains duplicates at indices 0 and 3.

Constraints:

• 1 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

Solution

There are a couple of popular ways to solve this problem. One approach is to using sorting. When we sort the given array, if there are any duplicates they will be placed adjacent to each other. Then we can easily iterate through the array and find out if there are any duplicates by comparing adjacent elements. However, since we need to sort the array, this algorithm has a time complexity of O(n log n).

If we are looking for a better time complexity, hashmap is the way to go! We can use the hashmap data structure to efficiently detect duplicates. Let's see how this works.

Algorithm

Below is the step-by-step explanation of the working of the algorithm:

1. Initialization:

   Initialize a hashmap, seenNums, that takes a integer key and boolean value.

2. Check for duplicates:

   Next, iterate through the given nums array from start to end. In each iteration perform the following operations:

   1. Check if we have encountered (seen) the current number before this iteration, by checking if it is present in the hashmap. If it is present in the hashmap (hashmap value for the current number is true), it means we have found a duplicate. Therefore, we return true as result.

   2. If hashmap does not have this number (hashmap value for the current number is false), we add the current number as hashmap key and value as true, to indicate that we have seen this number, so that it can be used in the next iterations to check duplicates.

3. Return false:

   If we reach the end of array, it means we have not found any duplicates, all the elements in the nums array are unique. Therefore, we return false indicating there are no duplicates.

Simulation

Below diagram show a pictorial depiction of the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Rust Solution

Complexity Analysis

Time Complexity

In the worst case, when all the elements in the nums array are unique, the algorithm iterates through the entire array to find the result. Therefore, in n is the size of the given input array, the time complexity is O(n).

Space Complexity

As we iterate through the input array we also need to add it to the hashmap if it is not a duplicate. In the worst case, if all the elements in the input array are unique, we will end up storing all the elements in nums array in the hashmap. So, in the worst case this algorithm has a space complexity of O(n).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.