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

1. Approach: We can leverage a HashSet to efficiently check for duplicates. HashSets provide constant time (O(1)) average complexity for add and contains operations.

2. Algorithm:

   • Iterate through the input array nums.
   • For each number num in nums:
     • Check if the HashSet already contains num.
     • If it does, we've found a duplicate, so return true.
     • If it doesn't, add num to the HashSet.
   • If the loop completes without finding a duplicate, return false.

Explanation

The HashSet acts as a lookup table. Adding an element takes constant time on average, and checking for the existence of an element also takes constant time on average. This makes the overall algorithm very efficient for larger input arrays.

Code (Java)

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>(); // Use a HashSet to store seen numbers

        for (int num : nums) {
            if (seen.contains(num)) { // Check if the number is already in the set
                return true; // Duplicate found
            }
            seen.add(num); // Add the number to the set
        }

        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. The HashSet operations (add and contains) have average time complexity of O(1).

• Space Complexity: O(n) in the worst case. The HashSet could potentially store all n elements if there are no duplicates. In the best-case scenario (all duplicates), the space complexity would be O(1). However, we analyze the worst-case scenario for Big O notation.