algoadvance

Leetcode 217. 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.

Example:

  1. Example 1:
    • Input: nums = [1,2,3,1]
    • Output: true
  2. Example 2:
    • Input: nums = [1,2,3,4]
    • Output: false
  3. Example 3:
    • Input: nums = [1,1,1,3,3,4,3,2,4,2]
    • Output: true

Clarifying Questions

Before we start solving the problem, here are a few clarifying questions and assumptions:

  1. What is the range of values for the integers in the array?
  2. What is the maximum length of the array?
  3. Are there any constraints on the space complexity?

Strategy

We can solve this problem using one of the following approaches:

  1. Using a Hash Set:
    • Traverse through the array and use a hash set to keep track of the elements we have seen so far.
    • If we encounter an element that is already in the set, return true.
    • If we finish the traversal without finding any duplicates, return false.
  2. Sorting the Array:
    • Sort the array and then check for consecutive duplicate elements.
    • If any two consecutive elements are the same, return true.
    • If no duplicates are found after sorting, return false.

Approach: We will use the hash set approach as it is more efficient in terms of time complexity.

Code

Here is the C++ code that uses a hash set to determine if the array contains any duplicates.

#include <vector>
#include <unordered_set>

class Solution {
public:
    bool containsDuplicate(std::vector<int>& nums) {
        std::unordered_set<int> seen;
        for(const int& num : nums) {
            // Check if the number is already in the set
            if(seen.find(num) != seen.end()) {
                return true;
            }
            // Insert the number into the set
            seen.insert(num);
        }
        // If we found no duplicates, return false
        return false;
    }
};

// Example usage
// int main() {
//     Solution solution;
//     std::vector<int> nums = {1, 2, 3, 1};
//     bool result = solution.containsDuplicate(nums);
//     std::cout << (result ? "true" : "false") << std::endl;  // Output: true
//     return 0;
// }

Time Complexity

This solution effectively balances time efficiency and space complexity well for typical constraints seen in coding interviews.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI