Data Structures

Contains Duplicate

Given an array of integers nums, return whether there are any duplicates.

Example:

\notag \begin{align*} &\texttt{nums = [9, 3, 4, 9]} \\ &\texttt{=> returns true (9 is a duplicate)} \\ \end{align*}

Hint: There's a data structure you can use to do this efficiently.

First Few Test Cases:

hasDuplicate([])
# False

hasDuplicate([7])
# False

hasDuplicate([7, 7])
# True

To solve this problem, we can loop through the $\texttt{nums}$ array, and keep track of all the numbers we've already seen. There's a duplicate if we got to a number we already saw, like this:

In order to quickly check if we've seen a number, we should use a data structure where we can lookup by numbers quickly. This is a good use for the set data structure, since you can quickly tell if a number is in a Set. The set for the above example looks like this:

Here's how to code this up using a Set:

def hasDuplicate(nums):
    alreadySaw = set() # declare empty set

    for num in nums:

        # check if the current number is in the set, takes O(1) time
        if num in alreadySaw:
            return True

        # add the current number to set, takes O(1) time
        alreadySaw.add(num)

    # if no duplicates showed up, return False
    return False

Time Complexity $O(n)$ . We loop over all $n$ numbers in $\tt nums$ . For every number, we check to see if it's is in the set, and then we add it to the set, both of which take $O(1)$ time. This is a total of $O(n)$ operations.

Space Complexity $O(n)$ . We have to store a set, which might contain all the numbers.

Suboptimal Solutions

The above solution is optimal because we used a Set. It would be much slower if we used an Array, because Arrays have $O(n)$ lookup time, while Sets have $O(1)$ lookup time. See here for more details:

Open SpoilerClose Spoiler

An array would be a bad choice for this, because you can't quickly tell if an element is an an array. This is because you need to lookup elements by index 0, 1, 2, and so on. Here's an Array for the above example:

Here's the above code if we used an Array instead of a Set:

#### suboptimal solution
alreadySaw = [] # declare empty array

for num in nums:

    # check if the current number is in array, takes O(n) time
    if num in alreadySaw:
        return True

    # add the current number to array, takes O(1) time
    alreadySaw.append(num)

return False

Time Complexity $O(n^2)$ . We loop through the entire array which has length $n\texttt{=len(nums)}$ . Every step in the loop, we check if the current number is in the $\texttt{alreadySaw}$ array, which takes O(n) operations (this is slower than a Set, which has $O(1)$ lookups). This is a total of n*O(n) = $O(n^2)$ operations.

Space Complexity $O(n)$ . We need to store the $\texttt{alreadySaw}$ array, which might contain all the numbers.

Another solution is to store nothing, and loop through the array multiple times. This is slow. Time is more precious than space, since we can't go back in time, but we can go back in space.

Open SpoilerClose Spoiler

For every index i, we check if we already saw that number by re-iterating through the whole array. This uses no extra space but wastes a lot of time.

# for every number i
for i in range(len(nums)):
    # check all the numbers before i to see if nums[i] already appeared
    for j in range(i):
        if nums[i] == nums[j]:
            return True
return False

Time Complexity $O(n^2)$

Space Complexity $O(1)$

Mark as Completed:

Submits:

hasDuplicate

Test your code to get an output here!

hasDuplicate(

)

Test your code to get an output here!