217. Contains Duplicate#

Difficulty: Easy

Link to Problem: To see the Contains Duplicate problem on LeetCode, click here!

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.

Constraints:

  • 1 <= nums.length <= \(10^5\)

  • \(-10^9\) <= nums[i] <= \(10^9\)

Solution:#

Here’s a Python function to solve this problem:

def containsDuplicate(nums):
    # Create an empty set to store unique elements
    unique_elements = set()
    
    # Iterate through the array
    for num in nums:
        # If the element is already in the set, return True
        if num in unique_elements:
            return True
        # Otherwise, add it to the set
        else:
            unique_elements.add(num)
    
    # If the loop completes without finding duplicates, return False
    return False

Explanation:#

  1. The containsDuplicate function takes a single argument, nums, which is the input integer array.

  2. Inside the function, an empty set called unique_elements is created. This set will be used to keep track of unique elements in the input array.

  3. The function then iterates through the input array nums using a for loop.

  4. For each element num in the array, it checks whether num is already in the unique_elements set using the if num in unique_elements: condition.

  5. If num is already in the set, it means there is a duplicate element in the array, and the function immediately returns True.

  6. If num is not in the set, it is added to the unique_elements set using unique_elements.add(num).

  7. The loop continues to the next element, and the process repeats.

  8. If the loop completes without finding any duplicates, it means that all elements in the array are distinct, and the function returns False.

The code efficiently utilizes a set data structure to keep track of unique elements while iterating through the array, allowing it to quickly detect duplicate elements. This code meets the problem’s requirements and constraints, as explained earlier.

Test cases#

# Example 1:
nums1 = [1, 2, 3, 1]
print(containsDuplicate(nums1))

True

# Example 2
nums2 = [1, 2, 3, 4]
print(containsDuplicate(nums2))

False

# Example 3
nums3 = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
print(containsDuplicate(nums3))

True

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code for the “Contains Duplicate” problem:

Time Complexity:

The primary operation that affects the time complexity is the for loop that iterates through the input array nums. In the worst case, the loop will iterate through all n elements of the array, where n is the length of the input array.

  • Iterating through the array: O(n)

Inside the loop, we perform two operations:

  1. Checking whether an element exists in the unique_elements set (if num in unique_elements). This operation has an average time complexity of O(1) for a set.

  2. Adding an element to the unique_elements set (unique_elements.add(num)), which also has an average time complexity of O(1) for a set.

Since these operations are performed for each element in the array, the overall time complexity remains O(n).

Space Complexity:

The space complexity is determined by the additional data structures used in the code, which are the unique_elements set.

  • unique_elements set: This set stores unique elements from the input array. In the worst case, if all elements in the input array are distinct, the set will store all n elements.

Therefore, the space complexity is O(n) because, in the worst case, the set’s size will grow linearly with the input array’s size.

In summary, the time complexity of the code is O(n), where n is the length of the input array, and the space complexity is also O(n) in the worst case. This code is efficient and meets the constraints of the problem.

Challenging Exercises:#

  1. K Duplicates: Modify the problem to return true if there are exactly K duplicate elements in the array. Write a function that takes an additional integer parameter K and returns true if there are exactly K duplicates.

  2. Frequency Count: Write a function that returns a list of all the elements that appear more than once in the array, along with their frequencies.