Problem Informations

• Problem Index: 217
• Problem Link: Contains Duplicate
• Topics: Array, Hash Table, Sorting

Problem Description

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

Explanation:

The element 1 occurs at the indices 0 and 3.

Example 2:

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

Output: false

Explanation:

All elements are distinct.

Example 3:

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

Output: true

Constraints:

• $1 \leq \text{nums.length} \leq 10^5$
• $-10^9 \leq \text{nums}[i] \leq 10^9$

Intuition

The problem requires checking whether there are any duplicate elements in the integer array nums. A straightforward approach to this problem involves leveraging the nature of sorted arrays: any duplicate elements will be consecutive when the array is sorted. This understanding directs the approach to first sort the array and then scan for consecutive elements that are identical.

Approach

The algorithm follows these steps:

1. Special Case Handling: If the array contains only one element, it is immediately concluded that there are no duplicates, hence returning false. This step can be seen as an optimization to avoid unnecessary computation.

2. Sorting the Array: Using a sorting function, the input array nums is sorted. After sorting, any duplicate elements that might exist in the array will now be positioned next to each other.

3. Checking for Duplicates: Iterate through the sorted array and check for consecutive elements. If any two consecutive elements are found to be equal, it indicates the presence of duplicates, and the function immediately returns true.

4. Final Conclusion: After iterating through the entire array, if no consecutive elements are found to be identical, the function concludes that there are no duplicates and returns false.

The algorithm primarily relies on the efficiency of the sorting process, which is $O(n \log n)$, where $n$ is the number of elements in the array. The subsequent linear scan for duplicates is $O(n)$, making the sorting step the dominant factor in the computing time. This approach efficiently checks for duplicates by leveraging the properties of sorted arrays.

Code

C++

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        // If there is only one element, we can't have duplicates
        if (nums.size() == 1) {
            return false;
        }
        
        // Sort the array to bring any duplicates together
        sort(nums.begin(), nums.end());
        
        // Iterate through the array to check for consecutive duplicate elements
        for (int i = 0; i < nums.size() - 1; i++) {
            // If two consecutive elements are the same, a duplicate is found
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        
        // If no duplicates were found, return false
        return false;
    }
};

Python

class Solution:
    def containsDuplicate(self, nums):
        # If there is only one element, we can't have duplicates
        if len(nums) == 1:
            return False
        
        # Sort the array to bring any duplicates together
        nums.sort()
        
        # Iterate through the array to check for consecutive duplicate elements
        for i in range(len(nums) - 1):
            # If two consecutive elements are the same, a duplicate is found
            if nums[i] == nums[i + 1]:
                return True
        
        # If no duplicates were found, return false
        return False

Complexity

• Time complexity: The primary operations in this code are sorting the array and iterating through it. The sorting operation dominates the time complexity and has a time complexity of $O(n \log n)$, where $n$ is the number of elements in the array nums. The iteration through the array to check for duplicates is $O(n)$. Thus, the overall time complexity is $O(n \log n)$.
• Space complexity: The space complexity is $O(1)$ if we disregard the space used by the sorting algorithm because the sort operation is done in-place. However, if the sort function uses additional space, the space complexity would depend on the sorting algorithm employed by sort. In most standard library implementations, this is $O(\log n)$ auxiliary space for the stack space during recursive calls.