What makes me start

I believe that every software developer has heard of Leetcode. And if you want to work for a FAANG company, practicing Leetcode questions is a must. As a young and still naive software developer, I wish I could get into a big tech company one day. So, from now on, I also start my Leetcode Journey. And I would love to share my journey with you all so that you could leave some comments on what I did right or wrong, and see how far I can go.

However, it is not a great strategy to do random questions at random times. Therefore, I decided to follow a set of Leetcode questions provided by Neetcode. 150 Leetcode questions with different topics. From easy to hard. And the first question would be Contains Duplicate.

Question: Contains Duplicates

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Examples:

Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Constraints:

1 <= nums.length <= 105
109 <= nums[i] <= 109

Thought process

Brute force— O(n²)

The most intuitive solution is always the brute-force solution. However, it is still worth being mentioned as we can improve our solution from here.

The easiest method would be finding duplicated values for each number in the list. If there is none for each number, we will then return false. Return true otherwise.

Here is the sample code:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] == nums[j]:
                    return True
        return False

As the code loops the nums array within a loop, the time complexity will be O(n²).

Using a set — O(n)

In the brute force method, we need to search the same list of numbers repeatedly for each number in the list, and each search requires O(n) time complexity. But is there a way that reduces the searching time to O(1)? Fortunately, there is. And that is called Set (or Hash Map, but it will not be used in this case.)

What is so special about Set is that each access to the element takes only O(1) time. Therefore, this particular data structure comes in handy when we want to search for a number existence.

And the way I use Set is fairly simple. We loop through the array once. And we check if the number exists in the Set for each number. Return true if it exists, and add the number to the Set if not.

Here is the implementation:

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        existences = set()
        for num in nums:
            if num in existences:
                return True
            existences.add(num)
        return False

Take away

Even though it is an easy question, there are still some things we can take away. And in this case, we learn that a Set is a handy tool to store the existence of values, and we can check the existence of the value in O(1) time.