Contains Duplicate

Problem Statement

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,2,3,1] returns true as 1 appears more than once

Solutions

1. Brute-force

for each element in array:                      <- O(N)
    for each element ahead of it in array:      <- O(N)
        if those two are same:                  <- O(1)
            return true

return false

2. Sorting

When we sort the array, the similar elements would get placed close to each other

sort the array                                              <- O(N*logN)

for each element in sorted array:                           <- O(N)
    if current element's next element is same as current:   <- O(1)
        return true

return false

bool containsDuplicate(vector<int> &nums) {
    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 \cdot logN) + O(N) = O(N \cdot logN) \)

3. Hashing

By using some space for the set, we can quickly check if an element was previouly added to it

create a hash-set

for each element in the array:                      <- O(N)
    if current element already exists in the set:   <- O(1) on avg.
        return true
    add current element to the set                  <- O(1) on avg.

return false

bool containsDuplicate (vector<int> &nums) {
    unordered_set<int> uniqueNums;
    for (auto &curr : nums) {
        // Duplicate found
        if (uniqueNums.find(curr) != uniqueNums.end()) {
            return true;
        }
        uniqueNums.insert(curr);
    }
    return false;
}

Above time complexity is for unordered_set in C++. However, if you use set, the insertion and find operations would take O(logN) time in worst-case. So, the final complexity would be O(N*logN)