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

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

Code

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

public 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;
    }
}
            

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

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

Explanation

• Using a Set: Leverage the property of a set to only store unique elements.
• Iteration and Check: Iterate through the input array. For each number, check if it's already present in the set.
• Duplicate Found: If the number is already in the set, it means a duplicate exists, so return true.
• No Duplicates: If the loop completes without finding any duplicates, return false.
• Time Complexity: O(N), where N is the number of elements in the array, as we iterate through the array once. Set operations (add and contains) take O(1) on average.
• Space Complexity: O(N) in the worst case, if all elements in the array are unique, the set will store all of them.

Note