Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

Solution: 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.

Examples

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: '1' is repeating.

Example 3:

Input: nums= [3, 2, 6, -1, 2, 1]
Output: true  
Explanation: '2' is repeating.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

.....

.....

.....

Like the course? Get enrolled and start learning!
Zachary Nelson

Zachary Nelson

· 2 years ago

I appreciate that 3 example solutions are given but they are not given in order from least to most optimal. It would be nice to at least callout which solution for problems is the most optimal solution.

A

Aye Ess

· 3 years ago

class Solution: def containsDuplicate(self, nums): numsSet = set(nums) return not (len(nums) == len(numsSet))
mil o

mil o

· 2 years ago

Is there a reason why this would not be a good solution? Maybe I am overlooking something here

const uniqueSet = new Set(nums); if (uniqueSet.size !== nums.length) { return true; }
Show 4 replies
Abhijit Gupta

Abhijit Gupta

· 2 years ago

The count operation on a HashSet does not make sense. Please check this line -

set.count(x) also has an average time complexity of O(1)."

Raúl Fiol

Raúl Fiol

· a year ago

I just found another solution using Set(): by copying each element into a new set. Since a set only stores distinct elements, if the number of elements in the input matches the size of the Set, it means there are no duplicates

function containsDuplicate(nums) { if(!nums || nums.length == 0){ return false; } let nums_copy = new Set(); for(let i = 0; i<nums.length;i++){ nums_copy.add(nums[i]); } return nums_copy.size == nums.length ? false:true; }
Show 1 reply
R

Rohi Anon

· 3 years ago

I have another thought of how to proceed with this problem, but the problem is, I do not know the space and time complexity of this.

My thought process is as follows. Add all the elements in the array into a hash set. Count the number of existing elements in the two collections and compare to see whether there are any duplicates. The list collection should be equal to the set collection if there are no duplicates and return true.

I.e.

def containsDuplicate(nums):

`from collections import Counter`

`return Counter(nums) == Counter(set(nums))`
Show 1 reply
H

himanshu1495

· 3 years ago

What if we need to use O(1) space and O(N) time is it possible?

Show 1 reply
E

Eslam Hossam

· 3 years ago

For approach 2, what is the difference between using set and using list since the if condition will check if the number is unique or not.

Show 1 reply
Calvin

Calvin

· 3 years ago

def containsDuplicate(nums): for i in range(len(nums)): if nums[i] in nums[1+i:]: return True return False
Show 1 reply
E

ethanedge

· 2 years ago

The explanation uses the variable name 'unique_set' but in the Java code solution it is called just 'set'.