OK.
This video was helping me contain duplicate problem.
Let's start with the problem description.
We're giving an array of integers over has to do is the point if the array contains any duplicates meaning
that we should return true if there is an element that appears at least twice in the array and otherwise
we'll just return false.
So for example does this array contain any duplicates.
And the answer in that case is yes the one has a duplicate.
So we'll return true let's see another example.
There's this array contain any duplicates the answer in that case is no.
Oh isn't that array are unique.
So we'll return false.
Now how can we actually generalize this.
How can we solve this.
Well first way to solve this is maybe through sorting well sort of an array pass over our sorted away.
And if we find two consecutive areas that have the same value then we've got a duplicate.
So we return true another way to solve this.
And this is actually a pretty good way is to utilize a set as you probably know a set is a data structure
that by default only keeps one instance of each element.
Meaning that is set by default doesn't allow for duplicates.
So if you add for example to do a set and then you attempt to add another to that second to won't be
added so we'll add all the elements of our array to a set then we'll compare the size of the set to
the size of the array of the sizes are the same.
That means that the array doesn't contain duplicates.
So we would return true otherwise if we found that the sizes of the set of the array are not the same
or which are false.
A third method to solve this and this is the one that we'll walk through is to use a hash map.
Will do so by first creating a map that we'll call em here in the pseudocode and will loop over our
input array.
So the variable num will be the current element in our loop the current element in our iteration now
cursing we'll do in the loop is that we'll check if the map contains the current development if it does
then that would mean that we have already seen that value in the array.
So we return true.
We haven't returned.
Then we'll need to keep track of the current elements.
We'll need to store the fact that we've seen that element will do so by saving the value as a key in
our map.
And it doesn't matter what the value is it could be one could be a boolean value it's indexing the array
wherever the value is doesn't matter.
We only care about the key really and after the loop is done.
If we haven't returned from the Loop yet that means that not once did we find a duplicate.
Not once did we enter that if condition so we return false by default.
Now let's do a walk through here.
We got our example array one two three and one and that rectangle on your right would be our hash map.
So initially that map will be empty.
Next we'll start our loop that would go over the input array.
That loop would of course begin at the beginning of the array.
So our current element is 1 and the first thing we'll do in the loop is checking if the map contains
our current value which is 1.
And the answer this time is no so will indicate that we've seen a 1 by adding it to our map.
After that we'll just continue the loop.
Now we're at 2 and again we did find the 2 in our map.
So we'll add it next.
We're at the 3 same question is it's 3 in the map then we see a 3 before and the answer again is now.
So add 3 to our map.
Now we're at the last element of the array a 1 and this time things are different this time when we
ask the question of whether we've got that element in the map or not.
The answer would be yes.
That means that we've seen that element before meaning that the current element is actually a duplicate
so we'll return true.
Now the complexity with this will be big oh of anywhere.
And it's the size of the inputs.
And that's because we'll do a single loop over our input as you can see here these space complexity
would also be big.
Oh then that's because we'll have a map a map that could hold at most all and elements in our input
array.
And that's pretty much it.
Now let's implement this in the next video.