Contains Duplicate

What do we need to check

Contains Duplicate basically asks us to check if elements in the given array are unique. We are returning True if this is not the case and False otherwise.

Example Input & Outputs

Common Approaches and Complexity Needs

There are of course many ways to solve this question as well as with any other programming question but we have some recommended time and space complexity which is O(n) for time and O(n) for space complexity.

Brute Force

The most naive and straightforward solution would be to check every element with all the other elements in the input array to see if any duplication exists. This approach would cost us O(n²) time complexity which is not desired here.

Sort Check

Another approach could be sorting the input array first which would take O(n log n) time with known sorting algorithms and then iterating through the new sorted array and just looking for consecutive elements to see if any duplication exists again which would take O(n) time and this approach at the end would take whole solution to be O(n log n) time and O(n) space.

Using Hashmap

It would be nice to remember which elements we've seen in the input array while iterating through it and once we come across any element more than once we could say that the input array definitely contains at least one duplicate which would be enough to finalize the process. The question only asks us to check if any duplication of the elements in the input array exists. And also this approach would cost us O(n) in time and O(n) in space in the worst case (case of returning False here).

And I am going to walk you through this approach. If you feel like you need more time on hashmaps in Python you could visit one of the datacamps tutorials on hashmaps here.

Solution

Here we are creating an empty hashmap myHashMap = {} which is a built-in dict type in Python. We could use set() as our lookup structure but it doesn't make any difference in terms of complexity.

As we iterate through nums for each element we are first checking whether we have that element in our hashmap. Here we are using the .get() method of dict in Python. .get() method returns the value of the keyed element if it exists and if not it returns None.

And also note that in line 5 we are assigning 1 just as a placeholder here. When we find that an element does not exist in our hashmap, we basically add it. And here we are one step closer to the solution since if we again encounter that element (else block) in the future we are going to see that not every element in the input array is unique so we will return True.

As the iteration goes on if we find that every element in the given array is only seen once (that is for all the elements we are in the if block) we can guarantee that the given array has uniqueness in terms of its element values. And so at the end of the loop we can return False.

Below you can see and play through the process yourself to see our hashmap's state in every step. I'd suggest use a pen and paper to spend some time on these steps so that it really sinks in.

def hasDuplicate(nums: List[int]) -> bool:
    myHashMap = {}
    for num in nums:
        if myHashMap.get(num) is None:
            myHashMap[num] = 1
        else:
            return True
 
    return False

Here you can see that we are using a hashmap for our space resource and it can only grow up to the size of the input array and since we are just iterating the whole input array once our time complexity is O(n) here. Note that .get() and assignment operations cost only O(1) on average.

And also our space complexity is O(n) and it actually happens in the worst case, the case of iterating through whole input.