Practice here

Given an integer array, return true if any value appears at least twice in the array, and return false if every element is distinct.

Brute Force#

The simplest approach is to compare every element against every other element. Use two nested loops — the outer loop picks each element and the inner loop checks all subsequent elements for a match. If any pair is equal, a duplicate exists. This is correct but wastes time revisiting the same pairs.

• For every element check if repeatition found.

Time Complexity: O(n²)

Space Complexity: O(1)

Better Approach: Sorting#

Sorting brings any duplicates next to each other, so a single linear scan is enough to detect them. Once sorted, if any element equals its neighbor, we have a duplicate; otherwise every element is distinct. This avoids the quadratic comparison of brute force by first paying an O(n log n) sort cost.

• Sort the elements
• Compare consecutive elements

class Solution {
public:
    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(nlogn)

Space Complexity: O(1)

Better Approach : HashSet#

A hash set gives O(1) average-time lookup, so we can detect duplicates in a single pass without sorting. As we iterate, we check whether the current element is already in the set — if yes, we've found a duplicate and return immediately; otherwise we insert it and move on. The trade-off is O(n) extra space for the set in exchange for the fastest possible time complexity.

• Use set to check repetition

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for(int i=0;i<nums.size();i++)
        {
            if(s.count(nums[i]))
                return true;
            s.insert(nums[i]);
        }
        return false;
    }
};

Time Complexity: O(n) (Refer Time complexity for unordered_set)

Space Complexity: O(n)

Summary#