217. Contains Duplicate

Description

The problem requires determining if there are any duplicate elements in an array of integers. If any value appears at least twice in the array, return true. If every element is distinct, return false.

Intuition

To find duplicates, sorting the array makes it easier to check if any two consecutive elements are the same. After sorting, any duplicates would be adjacent in the array, allowing for a simple comparison.

Approach

1. Sorting: - First, sort the array. Sorting places any duplicate elements next to each other.
2. Checking for Duplicates: - Iterate through the sorted array and compare each element to the previous one. - If two consecutive elements are equal, return true since a duplicate is found. - If the loop completes without finding any duplicates, return false.

Complexity

Time Complexity:

O(n log n), where n is the number of elements in the array. This is due to the sorting step, which dominates the overall time complexity.

Space Complexity:

• O(1) if the sorting is done in-place and no extra space is used.
• O(n) if the sorting algorithm requires additional space, such as in some implementations of merge sort.

Code

C++

class Solution {
public:
    bool containsDuplicate(std::vector& nums) {
        std::sort(nums.begin(), nums.end());
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        
        return false;
    }
};

Python

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        nums.sort()
        
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
                
        return False

Java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        
        return false;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var containsDuplicate = function(nums) {
    nums.sort((a, b) => a - b);
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            return true;
        }
    }
    
    return false;    
};