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.

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.

Constraints:

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

Solution

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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

Anonymous

· 2 years ago

in the article you wrote set.count(x), set doesn't have a count method

Show 1 reply
A

Anonymous

· 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)."

A

Anonymous

· 2 years ago

I'm confused why would the worst case scenario for approach 2 be O(n^2) when using a Set in JavaScript since if the number already exists in the set, the add operation would just be ignored and the code would just early return true? So shouldn't the worst case scenario for approach 2 still be O(n)?

Show 1 reply
A

Anonymous

· 3 years ago

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

A

Anonymous

· 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
A

Anonymous

· 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
A

Anonymous

· 3 years ago

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

Show 1 reply
A

Anonymous

· 4 years ago

class Solution:
    def containsDuplicate(self, nums):
      numsSet = set(nums)
      return not (len(nums) == len(numsSet))
Show 3 replies
A

Anonymous

· 4 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

Reading Progress

0%

Vote for new content