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:

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:

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:

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:

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.

Mark as Completed:

Submits:

hasDuplicate

Test your code to get an output here!

hasDuplicate(

)

Test your code to get an output here!