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 efficiently solve this problem using a hash set (or dictionary in Python). Hash sets provide constant time average complexity for insertion and lookup.

2. Algorithm:

   • Create an empty hash set called seen.
   • Iterate through the input array nums.
   • For each number num in nums:
     • Check if num is already present in the seen set.
     • If num is in seen, it means we've encountered a duplicate, so return True.
     • If num is not in seen, add it to seen.
   • If the loop completes without finding any duplicates, return False.

Explanation

The solution leverages the properties of a hash set. Hash sets allow for very fast checking of whether an element exists within the set. By iterating through the array and checking if each element is already in the set, we can determine if a duplicate exists in O(n) time on average. If we used a nested loop to compare each element to every other element, the time complexity would be O(n²), which is significantly less efficient.

Code

def containsDuplicate(nums):
    """
    Checks if an array contains duplicate numbers.

    Args:
      nums: A list of integers.

    Returns:
      True if the array contains duplicates, False otherwise.
    """
    seen = set()  # Use a set for efficient lookups
    for num in nums:
        if num in seen:
            return True  # Duplicate found
        seen.add(num)  # Add to set if not already present
    return False  # No duplicates found

Complexity

• Time Complexity: O(n) on average. In the worst case (all unique elements), we iterate through the array once. Hash set lookups and insertions are O(1) on average.

• Space Complexity: O(n) in the worst case. The seen set could potentially store all n elements if all elements are unique.