Duplicate Detection in Arrays

The objective of this problem is to determine whether any element in the array is duplicated. If an element appears twice, the task is to return true; otherwise, return false.

Example:

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

Output: true

Sorting Approach

One way to address this problem is by utilizing a sorting approach. The idea is to sort the array and check if any element in the ith position is equal to the element in the i+1th position. If a match is found, the function returns true.

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

• Time Complexity: O(n log n) due to sorting (where n is the number of elements in the array)
• Auxiliary Space: O(1) - constant space for sorting in place

Hash Map Approach

Another efficient approach involves using a hash map. In this method, we iterate through the array, checking if the current element already exists in the hash map. If it does, we return true; otherwise, we mark the element in the hash map. This approach has a linear time complexity.

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, int> umap;

        for(int i = 0; i < nums.size(); i++){
            if(umap[nums[i]] != 0){
                 return true;
            } else {
                umap[nums[i]] = 1;
            }
        }
        return false;
    }
};

• Time Complexity: O(n) - iterating through the array and accessing hash map operations
• Auxiliary Space: O(n) - to store elements in the hash map