deepSWE.io

Contains Duplicate

Hashing

10 min

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

Example 1:

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

Output: true

Solution (Hash Set)

The most efficient way to solve this problem is by using a hash set. We can iterate through the array, and for each element, check if it's already in the set.

Algorithm Steps

Initialize an empty hash set.
Iterate through each number in the input array.
For each number, check if it already exists in the hash set.
If it does, a duplicate has been found. Return true.
If it does not, add the number to the hash set.
If the loop completes without finding any duplicates, it means all elements are unique. Return false.

Input Array:

Array (nums)

Hash Set

Start with an empty hash set.

Contains Duplicate Solution


class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        hashset = set()
        for n in nums:
            if n in hashset:
                return True
            hashset.add(n)
        return False