217. Contains Duplicate

At a Glance

• Topic: arrays-hashing
• Pattern: Hash Set
• Difficulty: Easy
• Companies: Amazon, Apple, Google, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 217

Problem (one-liner)

Given an integer array numbers, return true if any value appears at least twice; otherwise return false.

Recognition Cues

• "Contains duplicate", "any element appears more than once"
• Unsorted array membership / uniqueness check

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n²) time / O(1) space — compare all pairs.
• Better — sort then scan adjacent — O(n log n) time / O(1) or O(n) space depending on sort.
• Optimal — O(n) time / O(n) space — hash set: insert each number; if already present, duplicate found.

Optimal Solution

Go

package main

func containsDuplicate(numbers []int) bool {
	seen := make(map[int]struct{})
	for _, value := range numbers {
		if _, exists := seen[value]; exists {
			return true
		}
		seen[value] = struct{}{}
	}
	return false
}

JavaScript

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

Walkthrough

Input: numbers = [1, 2, 3, 1]

Invariant: seen holds exactly the distinct values processed so far.

Edge Cases

• Length 0 or 1 → false.
• All equal → true after second element.
• Integer overflow not relevant for equality checks.

Pitfalls

• Sorting in O(n log n) when O(n) set suffices.
• Using an array as set without bounding range (works only for small bounded integers).

Similar Problems

• 001. Two Sum — map value → index; duplicate awareness.
• 128. Longest Consecutive Sequence — set as structure on distinct values.
• 242. Valid Anagram — counting duplicates as multiset.

Variants

• Return first duplicate.
• K-distinct elements window (sliding window family).
• Contains duplicate within distance k (needs extra structure).

Mind-Map Tags

#hashset #arrays #duplicate-detection #membership