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 to Solve

The most efficient way to solve this problem is to use a HashSet. A HashSet only stores unique elements. We can iterate through the input array and try to add each element to the HashSet. If an element already exists in the HashSet (meaning it's a duplicate), we immediately return true. If we iterate through the entire array without finding any duplicates, we return false.

Detailed Explanation

1. Initialize a HashSet: Create an empty HashSet of integers called seen. This will store the unique numbers encountered so far.

2. Iterate through the array: Use a foreach loop to iterate through each number (num) in the input array nums.

3. Try to add to HashSet: For each num, attempt to add it to the seen HashSet using the Add() method. The Add() method returns true if the element was successfully added (meaning it was unique), and false if the element already exists (meaning it's a duplicate).

4. Check for duplicates: If seen.Add(num) returns false, it means a duplicate was found. Immediately return true.

5. No duplicates found: If the loop completes without finding any duplicates, it means all elements are unique. Return false.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> seen = new HashSet<int>(); // Use a HashSet to efficiently track seen numbers
        foreach (int num in nums) {
            if (!seen.Add(num)) { // Try to add the number to the HashSet. If it already exists, Add() returns false.
                return true; // Duplicate found
            }
        }
        return false; // No duplicates found
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. HashSet operations (Add) have an average time complexity of O(1).

• Space Complexity: O(n) in the worst case. The HashSet could potentially store all n elements if all elements are unique. In the best case (all elements are duplicates except one), the space complexity would be O(1).