217. Contains Duplicate

217

EasyArrays and HashingHash setSeen-set membership

Contains Duplicate

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

In plain English

Decide whether the array contains any repeated element.

Picture it like this

Like collecting unique stamps into an album: if you end with fewer distinct stamps than pieces of paper you handled, some stamp was a repeat.

Example

Input: nums = [1, 2, 3, 1]
Output: true
Why: The value 1 appears at index 0 and index 3, so a duplicate exists.

Constraints

1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9

Pattern lesson

See the pattern, then code

Seen-set membership

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Distinctness means the count of unique values equals the length; any collapse in size proves a repeat.

New words, made simpleKnow these before the algorithm

Hash set: A collection that stores only distinct keys with average O(1) insert and lookup.
Cardinality: The number of distinct elements in a set.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force pairs

Too slow for n up to 10^5.

Compare every pair of indices for equality.

Time O(n^2)Space O(1)

Sort and scan neighbors

Faster but still beaten by hashing and it mutates order.

Sort, then check adjacent equal pairs.

Time O(n log n)Space O(1)

Best choiceSet cardinality

Simplest linear-time solution.

Build a set and compare its size to the array length.

Time O(n)Space O(n)

The rule we keep true

Invariant

A set never stores the same key twice, so its size equals the count of distinct values seen so far.

Why this is correct

Reasoning

Building a set from n values yields exactly the distinct values; if the resulting size is smaller than n, at least two positions shared a value, which is the definition of a duplicate.

The algorithm in three movesSay these aloud before coding

1Insert values into a set, or build a set from the whole array

set builds {1,2,3}

2Compare the number of unique values to the array length

len(set)=3 != len(nums)=4

3If they differ, at least one duplicate was collapsed, so return true

return true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read1,2,3,1

2 · AskHow many distinct?

3 · Update stateset = {1,2,3}

4 · ResultThe second 1 is absorbed without growing the set.

Key takeaway

The repeated 1 collapses in the set, shrinking its size below the array length.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Set comparison
set(nums) removes repeats; if that shrinks the count relative to len(nums), a duplicate was present, so the inequality is exactly the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-element array always returns false
All identical values returns true
All distinct values returns false
Negative numbers hash the same as any other integer

Common beginner mistakes

Using == instead of != and inverting the answer
An early-exit loop that adds to the set but forgets to check membership before inserting (still correct but the one-liner is cleaner)
Assuming sorting is free of side effects when the caller may reuse the array

Check your understanding

How would you return early to save memory when a duplicate appears near the front?

Contains Duplicate

Contains Duplicate

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing