Why use a hash set for Contains Duplicate?

A set answers "have I seen this value before?" in O(1) time on average, so one pass over the array is enough: O(n) time instead of the O(n²) of comparing every pair.

What is the time and space complexity of Contains Duplicate?

With a hash set: O(n) time on average and O(n) extra space. Sorting first and comparing neighbours takes O(n log n) time and O(1) extra space if the sort is in place.

Can I just compare the set size with the array length?

Yes: building a set from the whole array and checking whether it is smaller than the array also works in O(n). The one-pass loop is usually preferred in interviews because it stops at the first duplicate.

Contains Duplicate

Return true if any value appears at least twice in the array, using one pass with a hash set.

EasySolve on LeetCode

Problem Understanding

Contains Duplicate: given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.

Example: nums = [1, 2, 3, 1] returns true, because 1 appears at index 0 and index 3. nums = [1, 2, 3, 4] returns false.

Attempt 1: Compare Every Pair

Compare each nums[i] with every nums[j] for j > i, and return true on the first match. Two nested loops: O(n²) time, O(1) extra space. For each number, the inner loop is asking one question, did this value appear earlier?, and it answers by scanning.

The Intuition: Remember What You Have Seen

Walk the array once and keep every value met so far in a hash set.

If the current number is already in the set, it appeared earlier: return true.
Otherwise add it to the set and move on.

If the loop finishes, no value was ever met twice: return false. The set turns the inner scan into a single O(1) lookup.

Interactive Walkthrough

The array is scanned left to right while the set fills up beside it. On each step the current value is looked up: a miss adds it to the set, a hit fills the two cells that hold the repeated value and the answer is true.

Dry Run Table

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

`i`	`nums[i]`	In `seen`?	`seen` after
0	1	no, the set is empty	`{1}`
1	2	no	`{1, 2}`
2	3	no	`{1, 2, 3}`
3	1	yes	return `true`

The loop stops at index 3; nothing after the first repeat is read.

The Sorting Alternative

Sort the array, then compare each element with its neighbour: equal values end up next to each other. That is O(n log n) time and O(1) extra space with an in-place sort, but it changes the input. Interviewers often ask for both: the hash set when time matters, sorting when memory does.

The Solution Template

One pass with a hash set.

Contains Duplicate Code

1var containsDuplicate = function(nums) {
2    const seen = new Set();
3    for (const num of nums) {
4        if (seen.has(num)) {
5            return true;
6        }
7        seen.add(num);
8    }
9    return false;
10};

Edge Cases & Common Mistakes

One element: nothing to compare with, so the answer is false.
The repeat is at the very end: the whole array is scanned before true, which is still O(n).
Negative numbers and zero: a set handles them like any other value.
Using a list instead of a set: num in list is a linear scan, which brings back O(n²).

Summary

Contains Duplicate is the hash set version of the hash map pattern: replace "did this appear earlier?" with one lookup by remembering every value already seen, and stop at the first repeat. It is the same move as Two Sum, with membership instead of a complement.

More practice: DSA interview questions with answers · patterns cheat sheet

Two Sum

Valid Anagram