LeetCode 217: Contains Duplicate

Problem Description

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

Explanation: The element 1 occurs at indices 0 and 3.

Example 2:

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

Output: false

Explanation: All elements are distinct.

Complexity Analysis

Time Complexity: O(N)
We iterate through the array once. HashSet operations (contains, add) are O(1) on average.

Space Complexity: O(N)
In the worst case, all elements are unique, so we store all N elements in the HashSet.

Java Solution

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;  // Found duplicate!
            } else {
                set.add(nums[i]);  // Add to set
            }
        }
        return false;  // No duplicates found
    }
}

Intuition

The key insight is to use a HashSet to keep track of elements we've already seen as we iterate through the array.

Iterate Through Array: Process each element one by one from left to right.
Check HashSet: Before processing, check if the current element already exists in our HashSet.
Duplicate Found: If element exists in HashSet, we found a duplicate - return true immediately.
Add to HashSet: If element doesn't exist, add it to the HashSet and continue.
No Duplicates: If we finish the entire array without finding duplicates, return false.

Step-by-Step Code

Live Visualization

Input Array

Input Array:

HashSet Contents:

HashSet is empty

Algorithm States

Status: Ready Current Index (i): N/A Current Element: N/A HashSet Size: 0 Duplicate Found: false