6. Contains Duplicate

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.

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

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

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

Problem Breakdown:

1. We create a hash set to store numbers we have seen so far. Sets provide O(1) average time for both insertion and lookup.

• seen = set()

2. We iterate through each number in the array. For each number, we check if it already exists in our set.

• for num in nums:
      if num in seen:

3. If the number is already in the set, we found a duplicate and return True immediately.

•         return True

4. If the number is not in the set, we add it so future iterations can detect it as a duplicate.

•     seen.add(num)

5. If we finish iterating without finding duplicates, we return False.

• return False

Summary:

Use a hash set to track seen numbers. For each element, check if it exists in the set. If yes, return true. Otherwise add it. If no duplicates found after full iteration, return false.

Time and Space Complexity:

Time Complexity: O(n) - we iterate through the array once, and set operations are O(1) on average.

Space Complexity: O(n) - in the worst case, we store all n elements in the set.

Python Solution:

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

JavaScript Solution:

var containsDuplicate = function(nums) {
    const seen = new Set();
    for (const num of nums) {
        if (seen.has(num)) return true;
        seen.add(num);
    }
    return false;
};

Java Solution:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) return true;
            seen.add(num);
        }
        return false;
    }
}