Contains Duplicate

🔗 NeetCode Problem:
https://neetcode.io/problems/duplicate-integer/question?list=neetcode150 🔗 LeetCode Problem:
https://leetcode.com/problems/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.

Approach 1: Brute Force (Nested Loop)

Idea

Compare every element with every other element to check if a duplicate exists.

Pseudocode

for i from 0 to n-1:
    for j from i+1 to n-1:
        if nums[i] == nums[j]:
            return true
return false

C++ Implementation

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

Complexity Analysis

Time Complexity: O(n²) → Nested loops over the array
Space Complexity: O(1) → No extra space needed

Why it’s not optimal?

For large arrays, comparing every pair becomes extremely slow. If the array has 10,000 elements, we’d do ~50 million comparisons in the worst case.

Optimized Approach: Using Hash Map (Unordered Map)

Idea

Use a hash map to store elements as we iterate.
If an element already exists in the map, it means a duplicate is found.

Key Insight

Hash map lookup is O(1) on average, so we only need a single pass through the array.

C++ Implementation

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

        for (int i = 0; i < nums.size(); i++) {
            if (mp.find(nums[i]) != mp.end())
                return true;

            mp[nums[i]] = i;
        }
        return false;
    }
};

Complexity Analysis

Time Complexity: O(n) → Single pass through the array with O(1) lookups
Space Complexity: O(n) → Hash map stores up to n elements

Why it’s better?

Single pass with constant-time lookups beats nested loops. Early termination when duplicate is found.

Alternative Optimized Approach: Using Hash Set

Idea

Similar to hash map, but we only need to store the elements themselves, not their indices.

C++ Implementation

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;

        for (int num : nums) {
            if (seen.find(num) != seen.end())
                return true;

            seen.insert(num);
        }
        return false;
    }
};

Complexity Analysis

Time Complexity: O(n) → Single pass with O(1) lookups
Space Complexity: O(n) → Hash set stores up to n elements

Advantage over Hash Map

Hash set uses slightly less memory since we don’t store indices, only the elements themselves.

Optimized Approach: Using Sorting

Idea

Sort the array, then check if any adjacent elements are equal.

C++ Implementation

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;
    }
};

Complexity Analysis

Time Complexity: O(n log n) → Sorting dominates
Space Complexity: O(1) → In-place sorting (depending on sort implementation)

When to use?

When space is critical and you can afford sorting overhead. Not as good as hash-based approaches for time.

Comparison of All Approaches

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute Force	O(n²)	O(1)	No extra space	Very slow for large arrays
Hash Map	O(n)	O(n)	Fast, stores indices if needed	Uses extra memory
Hash Set	O(n)	O(n)	Fast, cleaner code	Uses extra memory
Sorting	O(n log n)	O(1)	Space-efficient	Slower than hash-based

Why Hash Set is Most Optimal

Single pass: O(n) time complexity
Fast lookups: O(1) average case for hash operations
Early termination: Returns true immediately when duplicate is found
Memory efficient: Stores only values, not indices like hash map
Simple code: Clean and easy to understand

Example Walkthroughs

Example 1: `nums = [1, 2, 3, 1]`

Using Hash Set:

seen = {}

i=0: num=1
  - 1 not in seen
  - seen = {1}

i=1: num=2
  - 2 not in seen
  - seen = {1, 2}

i=2: num=3
  - 3 not in seen
  - seen = {1, 2, 3}

i=3: num=1
  - 1 IS in seen ✓
  - Return true

Duplicate found! Time: O(4) = O(n)

Example 2: `nums = [1, 2, 3, 4]`

Using Hash Set:

seen = {}

i=0: num=1 → seen = {1}
i=1: num=2 → seen = {1, 2}
i=2: num=3 → seen = {1, 2, 3}
i=3: num=4 → seen = {1, 2, 3, 4}

Loop ends, no duplicate found
Return false

No duplicates. Time: O(4) = O(n)

Example 3: `nums = [99, 99]`

Using Hash Set:

seen = {}

i=0: num=99
  - 99 not in seen
  - seen = {99}

i=1: num=99
  - 99 IS in seen ✓
  - Return true (immediately!)

Duplicate found on second element! Very efficient.

Key Takeaways

Avoid brute force for this problem (O(n²) is too slow)
Hash Set is optimal for general use (O(n) time, O(n) space)
Sorting is an alternative if space is strictly limited
Early termination makes hash-based solutions even faster in practice
Hash Map only needed if you must track indices, otherwise use Hash Set

​Contains Duplicate

​Problem Statement

​Approach 1: Brute Force (Nested Loop)

​Idea

​Pseudocode

​C++ Implementation

​Complexity Analysis

​Why it’s not optimal?

​Optimized Approach: Using Hash Map (Unordered Map)

​Idea

​Key Insight

​C++ Implementation

​Complexity Analysis

​Why it’s better?

​Alternative Optimized Approach: Using Hash Set

​Idea

​C++ Implementation

​Complexity Analysis

​Advantage over Hash Map

​Optimized Approach: Using Sorting

​Idea

​C++ Implementation

​Complexity Analysis

​When to use?

​Comparison of All Approaches

​Why Hash Set is Most Optimal

​Example Walkthroughs

​Example 1: nums = [1, 2, 3, 1]

​Example 2: nums = [1, 2, 3, 4]

​Example 3: nums = [99, 99]

​Key Takeaways

Contains Duplicate

Problem Statement

Approach 1: Brute Force (Nested Loop)

Idea

Pseudocode

C++ Implementation

Complexity Analysis

Why it’s not optimal?

Optimized Approach: Using Hash Map (Unordered Map)

Idea

Key Insight

C++ Implementation

Complexity Analysis

Why it’s better?

Alternative Optimized Approach: Using Hash Set

Idea

C++ Implementation

Complexity Analysis

Advantage over Hash Map

Optimized Approach: Using Sorting

Idea

C++ Implementation

Complexity Analysis

When to use?

Comparison of All Approaches

Why Hash Set is Most Optimal

Example Walkthroughs

Example 1: `nums = [1, 2, 3, 1]`

Example 2: `nums = [1, 2, 3, 4]`

Example 3: `nums = [99, 99]`

Key Takeaways