Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Brainstorm

The array's duplicate elements can be scattered throughout, making them difficult to find, however if they were next to each other, we could simply compare adjacent elements to detect if they are duplicates of each other. To bring them next to each other, we could use sorting.

Approach #1: Sort and Compare Adjacent Elements

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

Time complexity: $$O(n log n)$$

C++'s STL sort takes O(n log n) time. After sorting, we perform a linear scan of the array which ends up being dominated by the time complexity of sorting.

Space complexity: $$O(1)$$

STL sort uses a different sorting algorithm depending on the situation, but if heapsort is used, then space is usually O(1).