Contains Duplicate (LeetCode #217)

Image by Erol Ahmed on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Maximum Product Subarray.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Contains Duplicate code challenge, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up if you’re here because it gave you a hard time. We’re all learners in this industry at different points along the same path.

I don’t want to waste any more of your time, so let’s get started!

Initial Setup 🏗

The first thing we should always do is understand the problem (see: Polya’s Problem Solving Techniques). The rules for the coding challenge on LeetCode say that:

1. We will take in a list of nums
2. If any number appears twice in the list, return a True boolean
3. If there are no duplicates in the list, return False

I’ll be using Python for the answer for this question since it’s a bit like a universal coding language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

I’ll be jumping right in and giving you an “optimal” way to solve the problem (although I’ll be writing it in a way that’s intentionally straightforward to understand). We won’t waste time talking about inefficient solutions.

You came here for an answer, right? You’re going to get a good one.

So… Let’s get to it.

Building Our Variables and Loop 🪣

The first thing we can do is to write a variable just inside our function that allows us to track numbers that we’ve already seen (like a bucket).

We can do this by initializing a dictionary:

The next thing we need to do is build out a for loop that will allow us to iterate over the nums list.

This is enough for us to start writing our conditional logic. We’ll be using an if / else statement here to conditionally do some logic.

Let’s Look Backwards 👀

While we could solve this problem by just writing another nested for loop, that would end up giving us a time complexity of O(n^2). We can do better than that!

Instead, we’ll use that tracker variable to check for (and store) values on each iteration of our loop.

For each number, we can check if it exists already in the tracker. If so, we can return True (because the list contains duplicates).

If we don’t find the number in our tracker, we can set it to track it for later. This is what that ends up looking like in code form:

We’re checking if num is in tracker and returning True if so. If not, we store that number to reference later.

If we get through the entire list of nums without returning True, that means there’s no duplicates. To handle that, we can just have a return False statement at the end of the function to handle all cases where there are no duplicates (or even if the list is empty).

This is what the solution to the coding challenge looks like:

This solution will run with O(n) time complexity (for iterating across the entire list of nums) and O(n) space complexity (for storing every number in the tracker).

Conclusion

Congrats! 🎉 You solved the problem.

I also hope you learned something as much as I enjoyed writing this.

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Also, feel free to reach out to me on any of the links below if you want to talk about coding, cool tech, or anything else (I love good book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)