algoadvance

217. Contains Duplicate

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.

Example 1:

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

Example 2:

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

Example 3:

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

Clarifying Questions

1. Q: What are the constraints on the input array nums? A: The array nums will have a length between 0 and (10^5), and the elements of nums will be integers in the range of (-10^9) to (10^9).

2. Q: Can we modify the input array? A: Yes, but for a more general solution, assume the input array should not be modified.

3. Q: What should the function return if nums is an empty array? A: If nums is empty, it will obviously contain no duplicates, so the function should return false.

Strategy

To determine if there are any duplicate elements in the array, we can use a set to keep track of the elements we have encountered so far:

1. Initialize an empty set.
2. Iterate over each element in the array nums.
3. For each element, check if it is already in the set:
   • If it is, return true (since we have found a duplicate).
   • If it is not, add it to the set.
4. If the loop completes without finding any duplicates, return false.

This approach is efficient because checking membership and adding elements to a set both have average time complexity of (O(1)).

Code

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

Time Complexity

• The time complexity is (O(n)), where (n) is the number of elements in the array nums. This is because each element is checked for membership in a set (average (O(1)) time) and potentially added to the set (also average (O(1)) time).
• The space complexity is also (O(n)) in the worst case, as we may need to store all (n) elements in the set if there are no duplicates.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?