Skip to main content

217. Contains Duplicate

easy

Determine whether an integer array contains any duplicate value. Tests set-based deduplication and the time/space tradeoff against sorting.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute-force compares every pair — O(n^2) for 10^5 input is too slow.

Hint 2

Two clean approaches: sort and check adjacent pairs, or use a set to record what you've seen.

Hint 3

Sets give you O(n) time at the cost of O(n) space. Iterate; if the current value is already in the set return true, else insert it.

Solution approach

Reveal approach

Walk the array once with a hash set. For each value, check if it's already in the set: if yes, return true; otherwise insert it and continue. If the loop finishes without finding a duplicate, return false. Alternative: sort then check pairs of adjacent elements for equality — O(n log n) time but O(1) extra space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Arrays practice problems

See all Arrays problems →