Problem 217

Question statement:

Given an integer array $\texttt{nums}$, return $\texttt{true}$ if any value appears at least twice in the array, and return $\texttt{false}$ if every element is distinct.

Solution

There are a lot of possible ways to solve this problem. The fastest I could think of makes use of hashing.

Main idea:

We run through the array, and at each step record see if the current element has been encountered (belongs to the hash set), and return true if so. If the current element hasn’t been encountered, then add it to the hash set and proceed.

The main advantage of this idea is that we don’t have to go through the array twice, or even fully in a lot of cases. If we were to check for dupelicates directly in the given array, then our search space is the entire array. However, if we store every distinct element in a hash set, then our search space is only the much smaller hash set (that has size $\leq \texttt{i}$ at step $\texttt{i}$).

Python has a built in data-structure $\texttt{set}$, built out of hash-tables and are optimized precisely for solving membership problems: They run at O(1) for membership checking.

Code:

def containsDuplicate(self, nums: List[int]) -> bool:
    encountered = set()
    for i in nums:
        if(i in encountered):
            return True
        encountered.add(i)
    return False

Comments:

Not a daily challenge problem. Today’s (12/28) challenge question was problem 1151.

Time complexity: O(n)

At the time of submission, the above solution passes leetcode submission cases in 426ms, beating 92.29% of users. It uses 33.8MB of memory, beating 25.60% of users.