Data Structures

Contains Duplicate

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


nums = [9, 3, 4, 9]=> returns true (9 is a duplicate)\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:

To solve this problem, we can loop through the nums\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:

Time Complexity O(n)O(n). We loop over all nn numbers in nums\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)O(1) time. This is a total of O(n)O(n) operations.

Space Complexity O(n)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)O(n) lookup time, while Sets have O(1)O(1) lookup time. See here for more details:

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.

Mark as Completed:
Test your code to get an output here!
Test your code to get an output here!