Contains Duplicate

Problem

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.

Constraints

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solution

The problem Contains Duplicate can be solved using a hash map or sorting. As hash map takes O(n) time complexity while sorting takes O(n * logn), I’ll use hash map implementation. If space complexity is limited, I’ll use sorting implementation which takes O(1) space complexity compared to O(n) space complexity of hash map implementation.

Implementation

class Solution
{
  public:
    bool containsDuplicate(vector<int> &nums)
    {
        unordered_set<int> hashmap;
        for (int num : nums)
        {
            if (hashmap.find(num) != hashmap.end())
                return true;
            hashmap.insert(num);
        }

        return false;
    }
};