Description
Decide whether an integer array contains a repeated value.
Solution
def contains_duplicate(nums):
seen = set()
for value in nums:
if value in seen:
return True
seen.add(value)
return FalseExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[4,1,4]]- Output
true
4 occurs twice.
Example 2
- Input
[[1,2,3]]- Output
false
All three values are distinct.
Example 3
- Input
[[0]]- Output
false
A single element cannot repeat.
Approach
Insert values into a set. A failed insertion identifies a repeat.
Time & space
O(n) expected time; O(n) space, for n values.