Pattern visualizer

Contains Duplicate

Sorting would work but costs O(n log n). A hash set answers 'have I seen this value?' in O(1), so one left-to-right pass suffices: check each value against the set BEFORE adding it — the instant a lookup hits, a repeat exists and we can stop early. Animated on: Given an integer array, return true if any value appears at least twice, otherwise false..

Hash-set membership scan

time O(n)space O(n)step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

line 2

Seed an empty set 'seen'. Walk i left to right asking one question per cell: is this value already in the set? A hit means a duplicate.

Pseudocode

1FUNCTION containsDuplicate(nums):
2  make an empty set of seen values
3  FOR i from 0 to (length of nums) - 1:
4    IF nums[i] is already in the set: RETURN true
5    add nums[i] to the set
6  RETURN false

← / → step · space play · Home restart

Where to practice Arrays

Practice Arrays problems All Arrays problems Back to roadmap