Contains Duplicate (LeetCode #217)

Introduction:

I'm diving into a very common interview question: "Contains Duplicate" (LeetCode #217). This problem is fantastic for understanding how to efficiently check for the presence of elements, and it beautifully illustrates the power of a specific data structure: the HashSet.

Understanding the Problem:

The problem is straightforward: Given an integer array nums, we need to determine if any value appears more than once in the array. If even one duplicate is found, we should return true. If all elements are unique, we return false.

Let's look at some examples:

• Input: nums = [1, 2, 3, 1]

  • Expected Output: true (because '1' appears twice)

• Input: nums = [1, 2, 3, 4]

  • Expected Output: false (all elements are unique)

• Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]

  • Expected Output: true (many duplicates here!)

My Thought Process & Approach:

When approaching "Contains Duplicate," my immediate thought goes to checking each number against every other number. This would involve nested loops, leading to a less efficient solution (O(N^2) time complexity). While it works, interviewers often look for more optimized approaches.

This is where the idea of quickly checking if I've already seen a number comes in. If I encounter a number and realize I've seen it before, then it's a duplicate! To do this efficiently, I need a data structure that allows for very fast lookups and additions.

This points directly to using a HashSet in Java. A HashSet stores unique elements and provides average O(1) time complexity for add() and contains() operations.

Here's the refined logic:

1. Initialize a HashSet: Create an empty HashSet to store all the numbers we encounter.

2. Iterate through the array: Go through each number (n) in the input array nums one by one.

3. Check for Duplicates: For each n:

   • First, ask the HashSet: "Have I seen this number n before (hs.contains(n))?"

   • If the answer is yes, it means n is a duplicate, so we immediately return true. We don't need to check any further!

4. Add to Set: If the answer was no (we haven't seen n before), then add n to the HashSet (hs.add(n)) so we remember it for future checks.

5. No Duplicates Found: If the loop finishes without ever returning true, it means we went through the entire array and never found a duplicate. In this case, we return false.

Java Code Implementation:

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

Time and Space Complexity Analysis:

• Time Complexity: O(N) (Average Case)

  • We iterate through the input array nums exactly once.

  • Inside the loop, hs.contains(n) and hs.add(n) operations on a HashSet take average O(1) time. In the worst case (no duplicates, or duplicate at the very end), the loop runs N times, making the overall time complexity linear, O(N).

  • In the best case (e.g., [1, 1, 2, 3]), it returns true almost immediately.

  • This is the optimal time complexity because, to guarantee no duplicates, you must examine every element at least once.

• Space Complexity: O(N) (Worst Case)

  • In the worst case (e.g., all elements in nums are unique), the HashSet will end up storing all N unique elements.

  • Therefore, the space required by the HashSet grows linearly with the size of the input array, resulting in O(N) space complexity. This is optimal for approaches using auxiliary space to track seen elements.