algoadvance

Leetcode 217. 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.

Clarifying Questions

  1. Is there any constraint on the size of the array?
    • The typical constraints can be: 1 <= nums.length <= 10^5.
  2. What is the range of the values in the array?
    • The values can typically be within the range -10^9 <= nums[i] <= 10^9.
  3. Can the input array be empty?
    • According to the constraints, the array will have at least one element.
  4. Do we need to consider the case of non-integer elements in the input array?
    • No, the array will contain only integers as per the problem statement.

Strategy

To solve this problem, we can use a HashSet to track the elements we have encountered so far. The idea is simple:

  1. Traverse through each element in the array.
  2. For each element, check if it already exists in the HashSet.
    • If it does, return true as we have found a duplicate.
    • If it doesn’t, add the element to the HashSet.
  3. If the loop completes without finding any duplicates, return false.

This approach ensures that we only traverse the array once and each lookup/addition operation in a HashSet is O(1) on average.

Code

Here is the Java implementation of the solution:

import java.util.HashSet;

public class ContainsDuplicate {
    public static boolean containsDuplicate(int[] nums) {
        // Create a HashSet to store unique elements
        HashSet<Integer> set = new HashSet<>();
        
        // Traverse the array
        for (int num : nums) {
            // Check if the element is already in the set
            if (set.contains(num)) {
                return true; // Duplicate found
            }
            // Add the element to the set
            set.add(num);
        }
        
        // No duplicates found
        return false;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 4};
        System.out.println(containsDuplicate(nums1)); // Output: false

        int[] nums2 = {1, 2, 3, 1};
        System.out.println(containsDuplicate(nums2)); // Output: true
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI