Contains Duplicate

Easy#217find a pair

You get an array of numbers. Find out whether some number appears in it at least twice. Our example: [4, 9, 1, 7, 9, 2] — yes, 9 appears twice.

217 Contains DuplicateWalkthrough · 1×

Example: [4, 9, 1, 7, 9, 2]. Below the array is the set of numbers seen so far.

041921374952seen—
not reached yetin the setcurrent numberthe repeat

Start with an empty set: no number seen yet

01/16
restart · back · play · step
Speed
1function containsDuplicate(nums):
2 seen = empty set
3 for each x in nums:
4 if x in seen:
5 return true
6 add x to seen
7 return false
state
seen
{}
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. All we need to know about a number is whether we have met it before. A set stores exactly that and answers at once, without walking back over the array.
  2. The first number already in the set is a repeat: the answer is true, and the rest of the array does not matter.
  3. If the array ends with no hit, every number went into the set as new, so all of them differ: false.

Complexity

Time O(n): one pass, a set lookup is O(1) on average. Sorting and comparing neighbours would take O(n log n). Memory O(n): the set may hold every number.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.