Contains Duplicate

Check whether any value appears more than once.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Contains Duplicate: A set keeps one entry per distinct value, so any duplicate makes its final size smaller than the input size.

Input and goalCheck whether any value appears more than once.

Start set constructionFor nums=[4,1,4,2], set(nums) begins empty before reading index 0.

set reads40114223

inputLength4setSize0actioninitialize unique set

saved stateempty

Recognize it

Use a set when the question asks whether any equality collision exists and the values themselves, not their positions or counts, determine duplication.

Keep true

After set construction has consumed a prefix, the set contains exactly one entry for every distinct value in that prefix, so its size grows only on first occurrences.

Reuse it

When only uniqueness matters, canonicalize values into a set and compare cardinality; retain counts or positions only when the follow-up question actually needs them.

Pattern: Set.

Simple idea: A set removes repeated values. A duplicate exists when the set is shorter than the input.

def contains_duplicate(nums: list[int]) -> bool:
   return len(nums) != len(set(nums))

Cost: $O(n)$ average time and $O(n)$ space.