OK.
So in this video we are going to solve the contains duplicates.
Problem now judging from the name of the problem you can tell that our job will be to see if an array
contains any duplicates.
Now consider this array for example.
Does this array contain any duplicates and it does the number one as a duplicate.
Does this array contain any duplicates.
And no it doesn't.
Each element in that array doesn't get repeated.
It has a number of occurrence of only one only happens once in the array.
So how can you solve this well.
There are multiple ways to solve this.
One way is to simply sort the array.
Then we do a pass over our sorted array and if two consecutive elements are the same we simply return
true.
Another way is to add all the elements that we have in the array in a set and we compare the sizes of
the set to the array size and of the sizes are the same we automatically return true.
Now another method that we can do is to loop over the array once then we'll see if the current element
exists in a hash map that we would create.
And if the current element does exist in the map already we return true.
That's not the case we would update our hash map with the current element.
Now if the loop exits meaning that the loop never did go into the return to condition then we automatically
return false so let's see an example using this hash my method that we will use so here we got this
array 1 2 3 1 and we got our empty hash map so we will loop over our array and we'll start with the
one and we will check the map in the hash map.
Answer is 1 in the hash map and the answer is no there is no one in the hash map.
So we added to our map and then we would continue with our loop same check is doing the map and the
answer is still no so we add 2 to our hash map.
Same thing when we continue with the loop is 3 in the map.
The answer is No.
So we added.
And then finally we'll get to the US element which is again 1 and we'll do the same check.
We'll see if one exists in our hash map.
And the answer this time is a yes then we automatically return true because that means that we've seen
a one before while traversing over our array.
So that means that the current one that we're on is a duplicate.
So this is the pseudocode for the logic that we just talked about.
First we create a map.
Then we loop over our array.
We do a check to see if the current element exists in the map and if it does we return true.
Otherwise we increment the number of occurrences of that element in our map.
Now as you can see the time complexity of this is of anywhere and is the size of our array and the space
complexity is the same because we do create an external map.