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.

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)