LeetCode #217: Contains Duplicate

https://leetcode.com/problems/contains-duplicate/

In this blog post, we’ll go through the steps to solve the “Contains Duplicate” problem in Python 3.

1. Create a function called “contains_duplicate” that takes an array of integers as its argument.
2. Create an empty set called “seen”. This set will be used to keep track of the numbers we’ve seen so far.
3. Iterate through the array using a for loop. For each number in the array, check if it’s in the “seen” set. If it is, return true; otherwise, add it to the set.
4. If we’ve iterated through the entire array and haven’t found any duplicates, return false.

Here’s the complete solution:

class Solution:
    def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

Space Complexity

We use a set to keep track of the numbers we’ve seen so far. The space complexity of this approach is O(n), where n is the number of elements in the array.

The reason for this is that in the worst case scenario, we may need to store all n elements of the array in the set. Each element takes up a constant amount of space, so the total space required is proportional to the size of the array.

Runtime Complexity

We can use a set to keep track of the numbers we’ve seen so far. The runtime complexity of this approach is O(n), where n is the number of elements in the array.

The reason for this is that we need to iterate through the array once to check each element. For each element, we can check if it’s in the set. If it is, we can return true; otherwise, we can add it to the set.

The time complexity of adding an element to a set is O(1) on average, and the time complexity of checking if an element is in a set is also O(1) on average. So the total time complexity of this approach is O(n), which means that as the size of the array increases, the time required to solve the problem will increase linearly.