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.

Leet Code:

https://leetcode.com/problems/contains-duplicate/description/

Examples

Example 1:

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

Example 2:

Input: nums = [1, 2, 3, 4]
Output: false

Example 3:

Input: nums = [1, 1, 1, 3, 3, 4, 3, 1, 1]
Output: true

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

1. 1 ≤ nums.length ≤ 10^5
   1. The array can be very large - up to 100,000 elements.
   2. This means:
      1. Avoid O(n^2) solutions (like nested loops) – they will be too slow.
      2. Aim for O(n) or O(n log n) solutions.
2. -10^9 ≤ nums[i] ≤ 10^9
   1. The values can be large positive or negative integers.
   2. This means:
      1. You cannot use array indexing tricks like arr[num].
      2. But you can a set or hashmap because they can handle large values.

Different Approaches

1️⃣ Brute Force Approach (TLE)

Intuition:

Check every pair – if any two are equal, return true.

Code:

#include <vector>
using namespace std;

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^2), where n is the size of input array.
  • Because of nested loops.
• Space Complexity:O(1)

2️⃣ Sorting Approach

Intuition:

Sort the input array, then iterate over the array and check for the element number for the same value.

Code:

#include <algorithm>
#include <vector>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i - 1]) return true;
    }
    return false;
}

Complexity Analysis:

• Time Complexity:O(n log n)
• Space Complexity:O(1)

3️⃣ Hashing

We can use the unordered_map or unordered_set.

Code:

#include <unordered_set> // For fast lookup of seen elements
#include <vector>        // For using vector
using namespace std;

// Function to check if the array contains any duplicate elements
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen; // Step 1: Create a set to store unique elements

    // Step 2: Iterate through each number in the array
    for (int num : nums) {
        // Step 3: If the number is already in the set, it's a duplicate
        if (seen.count(num)) return true;

        // Step 4: Otherwise, insert the number into the set
        seen.insert(num);
    }

    // Step 5: If we finish the loop with no duplicates, return false
    return false;
}

The count function returns:

• 1 = If the element num exists in the set
• 0 = If the element num does not exist

Another way:

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    // Function to check if any duplicate exists in the input vector
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> numSet; // Step 1: Create a set to store unique elements

        // Step 2: Loop through each number in the array
        for (int n : nums) {
            // Step 3: Check if the current number already exists in the set
            if (numSet.find(n) != numSet.end()) {
                // Step 4: If it does, we've found a duplicate — return true
                return true;
            }

            // Step 5: Otherwise, insert the number into the set
            numSet.insert(n);
        }

        // Step 6: If no duplicates were found, return false
        return false;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(n)