Hello everyone, in this post I want to explore a solution to the Contains Duplicates LeetCode problem using Swift. Most solutions use Python and I think it would be a good idea to try to use Swift to explore how well it behaves for the LeetCode style questions.

The Problem#

This problem states that we have an array of integers and it may contain some values that are duplicated, so we need to write a function that check if the given array contains any element more than once.

Here are some examples of valid inputs and outputs:

# Example 1
Input: nums = [1,2,3,1]
Output: true

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

Solution#

To solve this problem we need to find a way to count for at least one duplicity in the array, if this condition happens we can be sure that there are duplicates.

There are several approaches to solve this.

Brute force#

We could think that if we select each element and compare with each other we would end up finding the duplicate, this solution involves the use of two nested for.

As we can observe in the image, when we compare each element with every other element, we create a scalability problem as our data set grows.

As an example, in a worse case nested comparison, if we have $30$ elements, we would perform $900$ operations; for $900$ elements, it would be $810,000$. This is why $O(n^2)$ time solutions are problematic when dealing with large data sets. To achieve scalability, we need to optimize our solutions for faster algorithms.

func containsDuplicateBruteForce(_ nums: [Int]) -> Bool {
    for n in 0..<nums.count {
        for m in (n + 1)..<nums.count {
            if nums[n] == nums[m] { return true }
        }
    }
    return false
}

Our solution works but, as we mentioned before, it is not ideal due to its time complexity, resulting in $O(n^2)$. The problem here is that we are doing inefficient comparisons, we can do better.

Sets#

We are looking for duplicates, so one possible approach for this problem is to store somehow the elements in a new container that doesn’t allow duplicates, then we can add them and if some element was not able to be inserted we can be sure that there are duplicates.

What data structure have the property of not allowing duplicates? It’s the Set!

Lucky us, Swift already comes with a build-in Set data structure.

Sets are data structures that don’t allow duplicates. We can iterate over the array and insert each element into a new Set. If the insertion fails (i.e., the element already exists in the Set), we return true. Sounds easy enough, let’s code it!.

func containsDuplicate(_ nums: [Int]) -> Bool {
    // Define the Set of integers
    var set = Set<Int>()
        
    // Iterate over the array to generate the Set, if the set returns false we found a duplicate
    for num in nums where !set.insert(num).inserted {
        return true
    }

    // if all elements were inserted then there is no duplicated value
     return false
}

According to some pages, inserting into a Set in Swift uses internally a hash map, this mean that the insertion takes in average $O(1)$, making this solution $O(n)$.

This solution is already quite efficient because we are only iterating over all elements only once, but can we do a simpler code that express the same idea in a more concise way?

We are iterating over the elements to create a new container with its own copy of values, at the end we will end up with two objects. We can take advantage of this in the following manner: if the number of elements on both containers is not the same, then we can assume there are duplicates, in case that both contains the same number of elements we can be sure that there are no duplicates. This solution may lead us to a more expressive and concise code, so let explore it.

func containsDuplicate(_ nums: [Int]) -> Bool {
    // Define the Set of integers
    var set = Set<Int>()
        
    // Iterate over the array to generate the Set, if the set returns false we found a duplicate
    for num in nums {
        set.insert(num)
    }

    // if both containers have the same number of elements, they are equal and no duplicates were found, conversely there are duplicates 
     return set.count < nums.count
}

This is looking simpler to read, but there is one last thing. Set constructors can accept Arrays to instantiate them, we could use this handy property to make a one line solution!.

func containsDuplicate(_ nums: [Int]) -> Bool {
    // If the count of unique elements in the Set is less than the total count, there are duplicates
    Set(nums).count < nums.count
}

This simple line of code solves the problem in an elegant and concise way, we are creating a new set and then calling .count on it, then we use that value to compare it to the size of the original array and returning the result.

The final time complexity of this solution is $O(n)$, because we are implicitly iterating over the array when we create the Set.

Conclusion#

I hope this post helps you understand how Swift features can be used to create elegant and efficient solutions. Thanks for reading, and until next time!