How do you approach Contains Duplicate?

A Set stores only unique elements.

What is the time complexity of Contains Duplicate?

Time complexity: O(n). Space complexity: O(n).

What are common mistakes on Contains Duplicate?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

Sitelet https://gitgood.dev/coding/contains-duplicate

gitGood.dev

← Back to problems

Contains Duplicate

EasyData Structures

Description

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

Example 1

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

Output: true

Example 2

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

Output: false

Example 3

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

Output: true

Constraints

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

Contains Duplicate: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

A Set stores only unique elements.
If a Set's size is less than the array length, there must be duplicates.
Or check if an element exists in the Set before adding it.

The optimal approach

Show the approach: Hash Set

Use a Set to track seen elements. If we encounter an element already in the Set, we found a duplicate.

Time: O(n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.

← Back to problems

Contains Duplicate

EasyData Structures

Description

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

Example 1

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

Output: true

Example 2

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

Output: false

Example 3

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

Output: true

Constraints

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

Contains Duplicate: approach, complexity and pitfalls

An easy arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

A Set stores only unique elements.
If a Set's size is less than the array length, there must be duplicates.
Or check if an element exists in the Set before adding it.

The optimal approach

Show the approach: Hash Set

Use a Set to track seen elements. If we encounter an element already in the Set, we found a duplicate.

Time: O(n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.