Contains Duplicate easy

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.

Example 1:

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

Example 2:

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

Steps

1. Approach: We can leverage a hash set (unordered_set in C++) to efficiently check for duplicates. Hash sets provide constant time complexity (O(1) on average) for insertion and lookup.

2. Algorithm:

   • Iterate through the input array nums.
   • For each number num in nums:
     • Check if num is already present in the hash set.
     • If num is already in the hash set, it means we've encountered a duplicate, so return true.
     • If num is not in the hash set, insert num into the hash set.
   • If the loop completes without finding any duplicates, return false.

Explanation

The hash set acts as a quick lookup table. When we encounter a number, we check if it's already in the set. If it is, we know it's a duplicate. If it's not, we add it to the set so we can quickly identify it as a duplicate if it appears again later. This avoids nested loops, resulting in a much more efficient solution than a brute-force approach (which would have O(n^2) time complexity).

Code

#include <iostream>
#include <vector>
#include <unordered_set>

class Solution {
public:
    bool containsDuplicate(std::vector<int>& nums) {
        std::unordered_set<int> seen; // Use a hash set to store seen numbers
        for (int num : nums) {
            if (seen.count(num)) { // Check if the number is already in the set
                return true; // Duplicate found
            }
            seen.insert(num); // Add the number to the set
        }
        return false; // No duplicates found
    }
};

int main() {
    Solution solution;
    std::vector<int> nums1 = {1, 2, 3, 1};
    std::vector<int> nums2 = {1, 2, 3, 4};
    std::cout << "Contains duplicate (nums1): " << solution.containsDuplicate(nums1) << std::endl; // Output: true
    std::cout << "Contains duplicate (nums2): " << solution.containsDuplicate(nums2) << std::endl; // Output: false
    return 0;
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Hash set operations (insertion and lookup) take O(1) average time.

• Space Complexity: O(n) in the worst case. The hash set could potentially store all n numbers if there are no duplicates. In the best case (all duplicates), the space complexity would be smaller.