So today let's solve contains duplicate.

This is another problem from the blind 75 list of questions we've been working on.

So I like this problem because it's a good problem for beginners, but there's also multiple solutions to it that I'd like to go over in this video.

So we're given an array of numbers.

We want to return true if there's any value in that list of numbers that appears at least twice, but maybe it could appear three times or four times, right?

Just at least twice, and we want to return false.

If there aren't any values that appear at least twice, basically what that means is that every value in the array is distinct.

So let's take a look at an example.

We have one, two, three, and then we have one again.

So of course this has duplicates, right?

So we return true.

And the easiest way we would be able to detect that is by brute forcing this.

So given these numbers, the first thing we do is look at the first number.

It's one.

How do we know if this is a duplicate or not?

Well, we'd have to compare it to every single number in the rest of the array.

So that would be a big O of n time operation just to check if the first number is a duplicate or not.

And then we'd have to do that for every number.

Then we have to check, is the second number a duplicate?

How do we know?

We have to compare it to every other number.

We do the same thing with the third one and the last one.

And so since we're doing it for every number in the array, the overall time complexity is going to become n squared.

And by the way, in this case, n is just the size of the input array.

So the brute force solution is big O n squared time complexity.

But the good thing is we don't need any extra memory.

So the memory complexity is big O of one.

It's definitely not a bad solution, but the question is, can we do better than that?

And yes, we definitely can.

A second approach that will help us is sorting.

What happens if we took this array and we sorted it?

It would look a little bit different.

It would look like this.

Okay.

But how does sorting help us?

Well, let's think about it.

If we sort the input, then any duplicates that do exist in the array, and clearly we see that two duplicates exist at the beginning of the array, they're going to be adjacent.

So when we're trying to detect any duplicates in here, we only have to iterate through the array once.

And as we do that, we're just going to be comparing two neighbors in the array, checking if they're duplicates.

Next, we're going to shift our pointers to the next spot.

Are these duplicates, are these duplicates, et cetera, et cetera, until we finish the entire array.

In this case, we see that these two adjacent values are duplicates, so we can return true.

And what's the time complexity of this?

Well, the one pass is just going to be big O of N, but we know that sorting does take extra memory, or not extra memory, it does take extra time complexity, and that time complexity is N log N.

So that's the bottleneck in this solution.

But again, we don't need extra space if you don't count the space that's used by the sorting algorithm.

So in this case, we do have a slightly better solution than brute force.

But actually, if we use a little bit extra memory, and it's really a trade-off, if we sacrifice space complexity, we can actually achieve better memory complexity, and let me show you how.

So suppose we don't sort our input, we're given the default input, but we use extra memory.

We use a hash set.

But what exactly is a hash set going to do for us?

It's going to allow us to insert elements into the hash set in big O of one time.

But it's also going to allow us to check.

We can ask our hash map, does a certain value exist?

We want to know, does this one exist in the hash map?

Well, if we start at the beginning of the array, so far, nothing is in our hash map.

So a one does not exist in our hash map.

That means this one is not a duplicate.

You can see that this is an improvement over the brute force.

Previously, to determine if this was a duplicate, we had to check every other value in the array.

This time, we don't.

But after we have checked if this is a duplicate, we do have to add it to our hash set.

Because later on, if we encounter a one, like over here, then we determine that this is a duplicate because we know that there's already a one in our hash set.

So next we're going to check two, two is not a duplicate.

Add it here.

Is three a duplicate?

Nope.

Add it here.

One.

Is this a duplicate?

Yep.

There's a one over here.

So we return true.

This does contain duplicates.

And by the way, since each operation was just big O of one, we had to do that for every value in the input array.

And we only had to scan through the list of inputs once.

The time complexity is going to be big O of n.

But the space complexity, we did have to sacrifice a little bit.

We have to create a hash set.

And the memory that that hash set will use could be up to the size of the input array, which is n.

So we do end up using extra memory.

But that's not too bad.

This is about as efficient as we can get in terms of time complexity.

So let's get into the code now.

Okay, so now let's get into the code.

So the first thing I'm going to do is create that hash set.

In Python, you can do that just like this.

It's just called a set.

And then the simple thing is just going through every value in the input array nums.

And before we end up adding it to our hash set, because remember, we want to add every one of these values to our hash set just like this.

But before we even do that, we want to know, is n a duplicate?

Does this value already exist in our hash set?

And if it does, we know that our array contains duplicates.

So we don't even have to continue through the rest of the array.

We can immediately return true because we found a duplicate.

But if it doesn't contain a duplicate, we're going to add that value, then iterate through the rest of the array of nums, and then the loop will exit.

And then we can return false to indicate that we did not find any duplicates in the array.

Now let's run the code to make sure that it works.

And on the left, you can see that, yes, it does work, and it is about as efficient as we can get.

So I really hope that this was helpful.

If it was, please like and subscribe.

It supports the channel a lot.

Consider checking out my Patreon where you can further support the channel.

And hopefully I'll see you pretty soon.

Thanks for watching.