LeetCode 217: Contains Duplicate

code
arrays and hashing
easy
Author

spa-dev

Published

May 28, 2024

Problem Description

Difficulty: Easy

Given an integer array nums, return True if any value appears more than once in the array, otherwise return False.

Example 1:

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

Output: True

Example 2:

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

Output: False

Initial Solution

This was really quite easy, using the Python set() function to create a set of unique numbers. We just need to ensure it returns True if the amount (length) of numbers in the set is different to that of the original list. Hence, the not operator is used below. Alternatively, replace == with != for the same result.

Note that set() will not retain the order of the list, so we must compare its overall length and not try to compare the content one-by-one (or convert it to a list and see if the two lists match exactly).

from typing import List
class InitialSolution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        return not len(set(nums)) == len(nums)
nums1 = [1, 2, 3, 3]
nums2 = [1, 2, 3, 4]
solution = InitialSolution()
print(solution.hasDuplicate(nums1))
print(solution.hasDuplicate(nums2))

Initial Results

Success. This solution passes the full suite of tests on NeetCode.

NeetCode Solution

The following code makes it clear that we are using a hashset to store the values. It does not create the entire set all at once (like we do above, always giving O(n) time complexity as it runs through the whole list). Instead, it goes step by step; thus only in the worst case would this be O(n). We must create the hashset, which in the worst case uses O(n) space.

class Solution:
    def hasDuplicate(self, nums: List[int]) -> bool:
        hashset = set()
        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False
solution = Solution()
print(solution.hasDuplicate(nums1))
print(solution.hasDuplicate(nums2))

Conclusion

An easy start to NeetCode problems. The solution has a worst-case complexity of:

  • Time complexity: O(n)
  • Space complexity: O(n)