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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Contains Duplicate and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →