Blind 75Easy

Contains Duplicate — Hash Set Membership

Track seen numbers in a set; if a value appears twice, return true immediately.

Hash SetArray

View problem on LeetCode

Problem Statement

Return true if any value appears at least twice in the array.

Why This Problem Matters

Simple membership check emphasises constant-time lookups.
Sets the stage for frequency-based problems.
Often used as an early warm-up in interviews.

Thought Process

Use a hash set

Insert numbers as you iterate; duplicates trigger immediate success.

Consider sorting alternative

Sorting and scanning adjacent pairs also works but costs O(n log n).

Return early on duplication

Stop the scan once a duplicate is found for optimal runtime.

Step-by-Step Reasoning

Initialise empty HashSet.
For each num, if set contains num return true.
Otherwise add num and continue.
Return false after loop.

Dry Run

nums = [1,2,3,1]

Duplicate 1 found when revisiting.

nums = [1,2,3,4]

Loop completes without duplicates; return false.

Complexity Analysis

Time

O(n)

Space

O(n)

Why

Each insert and lookup expected O(1); set can store up to n elements.

Annotated Solution

JAVA

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

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

HashSet.add returns false when the element already exists, delivering O(1) duplicate detection.

Common Pitfalls

Using a list instead of set leads to O(n^2) behaviour.
Neglecting to return early fails to take advantage of immediate detection.
For very large arrays, mention memory considerations and sorting alternative.

Follow-Up Questions

How do you detect duplicates at most k apart? (Use sliding window set.)
Can you count duplicates instead of just detecting them?

Key Takeaways

Hash sets are perfect for simple membership tests.

Remember alternative approaches when memory is constrained.

Early returns reduce unnecessary processing.