How to Solve the Contains Duplicate Problem in Swift

The Contains Duplicate problem is a typical algorithmic challenge where the task is to determine whether a given array of integers contains any duplicate elements. It’s a common problem in coding interviews and real-world applications that involve working with unique data.

In this post, we will explore multiple ways to solve the problem in Swift, starting with a brute-force approach, then an optimized sorting-based approach, and finally the most efficient solution using a Set.

Problem Definition

You are given an array of integers nums. Your task is to determine if any value appears at least twice in the array. The function should return true if any value appears more than once, and false otherwise.

Example:

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:

• The length of the array can be up to (10^5) elements.
• Each element in the array can range from (-10^9) to (10^9).

Let’s explore three different ways to solve this problem using Swift.

Solution 1: Brute-Force Approach

Approach:

In the brute-force approach, we compare every element with every other element in the array to see if they are the same. If we find any duplicates, we return true. If no duplicates are found after all comparisons, we return false.

Code Implementation:

func containsDuplicate(_ nums: [Int]) -> Bool {
    for i in 0..<nums.count {
        for j in i + 1..<nums.count {
            if nums[i] == nums[j] {
                return true  // Duplicate found
            }
        }
    }
    return false  // No duplicates found
}

// Test the function
let nums = [1, 2, 3, 1]
print(containsDuplicate(nums))  // Output: true

Time and Space Complexity:

• Time Complexity: O(n²) due to two nested loops.
• Space Complexity: O(1), since no extra space is used aside from a few variables.

Explanation:

This solution uses two nested loops: the outer loop selects an element, and the inner loop compares it with every subsequent element. If two elements are the same, the function returns true. If no duplicates are found after all comparisons, the function returns false.

Drawbacks:

The brute-force approach is inefficient for large arrays due to its O(n²) time complexity, making it impractical for arrays with thousands of elements or more.

Solution 2: Sorting Approach

Approach:

A more efficient way to solve this problem is to sort the array first. Once sorted, any duplicate elements will appear next to each other. We can then simply check if any two consecutive elements are the same.

Code Implementation:

func containsDuplicate(_ nums: [Int]) -> Bool {
    var nums = nums  // Create a mutable copy of the array
    nums.sort()  // Sort the array
    for i in 1..<nums.count {
        if nums[i] == nums[i - 1] {  // Compare adjacent elements
            return true
        }
    }
    return false  // No duplicates found
}

// Test the function
let nums = [1, 2, 3, 1]
print(containsDuplicate(nums))  // Output: true

Time and Space Complexity:

• Time Complexity: O(n log n) because sorting the array dominates the time complexity.
• Space Complexity: O(1) if sorting is done in place (Swift’s sort() method sorts the array in place).

Explanation:

This approach first sorts the array using Swift’s built-in sort() method, which has a time complexity of O(n log n). After sorting, we iterate through the array and compare consecutive elements. If any two consecutive elements are the same, we return true. If no duplicates are found, the function returns false.

Benefits and Drawbacks:

• Benefits: More efficient than the brute-force approach because sorting reduces the number of comparisons.
• Drawbacks: Sorting modifies the original array, and although it is faster than the brute-force approach, it still has a time complexity of O(n log n).

Solution 3: Using a Set (Optimal Solution)

Approach:

The most efficient way to solve this problem is by using a Set. A Set is a data structure that stores unique values. As we iterate through the array, we can check if the current element is already in the set. If it is, we return true because it means a duplicate exists. Otherwise, we add the element to the set and continue.

Code Implementation:

func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()  // Create an empty Set to store unique elements
    for num in nums {
        if seen.contains(num) {  // Check if the element is already in the Set
            return true  // Duplicate found
        }
        seen.insert(num)  // Add the element to the Set
    }
    return false  // No duplicates found
}

// Test the function
let nums = [1, 2, 3, 1]
print(containsDuplicate(nums))  // Output: true

Time and Space Complexity:

• Time Complexity: O(n) since we iterate through the array once, and Set operations (insertions and lookups) take O(1) time on average.
• Space Complexity: O(n) due to the extra space used by the Set to store the elements.

Explanation:

This solution uses a Set to store unique elements as we iterate through the array. For each element, we check if it already exists in the set. If it does, we return true. If it doesn’t, we add the element to the set. If no duplicates are found by the end of the loop, we return false.

Benefits and Drawbacks:

• Benefits: This solution is the most efficient in terms of time complexity, with linear performance. It also does not modify the original array.
• Drawbacks: The only drawback is the extra memory needed to store the set, but the trade-off for performance is generally acceptable.

Edge Cases

When solving the Contains Duplicate problem, it’s important to consider various edge cases to ensure that the solution is robust and works across different scenarios. Below are some critical edge cases that should be taken into account when implementing the solution in Swift:

1. Empty Array:

If the input array is empty, there are no elements to compare, so the function should return false.

Example:

let nums: [Int] = []
print(containsDuplicate(nums))  // Output: false

• Expected Output: Since there are no elements, there cannot be any duplicates, so the output should be false.

2. Array with One Element:

If the input array contains only one element, it’s impossible to have duplicates, so the function should return false.

Example:

let nums = [1]
print(containsDuplicate(nums))  // Output: false

• Expected Output: Since there is only one element, it cannot have duplicates, so the output should be false.

3. Array with All Unique Elements:

If the input array contains all unique elements (i.e., no duplicates), the function should return false.

Example:

let nums = [1, 2, 3, 4, 5]
print(containsDuplicate(nums))  // Output: false

• Expected Output: Since all elements in the array are unique, the function should return false.

4. Array with All Duplicate Elements:

If the input array consists entirely of the same element repeated multiple times, the function should return true.

Example:

let nums = [1, 1, 1, 1, 1]
print(containsDuplicate(nums))  // Output: true

• Expected Output: Since every element in the array is the same, the function should return true.

5. Array with Negative Numbers:

The array may contain negative numbers. The solution should correctly handle these and return whether duplicates exist.

Example:

let nums = [-1, -2, -3, -1]
print(containsDuplicate(nums))  // Output: true

• Expected Output: Since the element -1 appears twice, the function should return true.

6. Array with Negative and Positive Numbers:

The array may contain both negative and positive numbers. Ensure the function correctly handles and distinguishes between them.

Example:

let nums = [-1, 2, -3, 3]
print(containsDuplicate(nums))  // Output: false

• Expected Output: Since all elements are unique, the function should return false.

7. Array with Zeros:

The array may contain zero values. The function should handle multiple zeros correctly.

Example:

let nums = [0, 1, 2, 0]
print(containsDuplicate(nums))  // Output: true

• Expected Output: The element 0 appears twice, so the function should return true.

8. Array with Mixed Duplicates and Unique Elements:

The array may contain a combination of unique and duplicate elements. The function should return true as soon as a duplicate is found.

Example:

let nums = [1, 2, 3, 2, 4]
print(containsDuplicate(nums))  // Output: true

• Expected Output: The element 2 appears twice, so the function should return true.

9. Array with Large Numbers:

The array may contain very large or very small integer values within the range [-10^9, 10^9]. Ensure that the solution handles large inputs correctly.

Example:

let nums = [-1000000000, 1000000000]
print(containsDuplicate(nums))  // Output: false

• Expected Output: Since the two elements are different and within the valid range, the function should return false.

10. Array with Maximum Length (100,000 elements):

If the array contains the maximum number of elements (100,000), the solution should handle the large dataset efficiently. This is particularly important for the brute-force solution, which may fail or run slowly for such large input sizes.

Conclusion

In this post, we explored three different approaches to solve the Contains Duplicate problem in Swift:

1. Brute-force approach: A simple but inefficient solution with O(n²) time complexity.
2. Sorting approach: A more efficient solution with O(n log n) time complexity but modifies the original array.
3. Set approach: The optimal solution with O(n) time complexity and O(n) space complexity, making it the best choice for large datasets.

In practice, the Set-based solution is typically the best option due to its efficiency and ease of implementation.