Repeated Value Check
Problem
Given a list of values, decide whether any value shows up more than once. Return true if at least one value repeats anywhere in the list, and false when every value is unique. The repeats do not have to be next to each other.
Examples
Input: items = [4, 1, 9, 1]
Output: True
Why: the value 1 appears at two different positionsInput: items = [4, 1, 9]
Output: False
Why: all three values differInput: items = []
Output: False
Why: edge case, an empty list cannot contain a repeatHints
0 / 3
Comparing every pair answers the question but does far more work than needed. Think about what you would write down while reading the list once.
The only question at each element is whether you have met that value before, which is a membership test rather than a search.
Keep a collection of values already seen. For each element, check membership first and stop immediately with a positive answer if it is there, otherwise add it and continue. Reaching the end means everything was unique.
Solution
A set of already-seen values turns the repeated-value question into a constant-time membership test. Walking the list once and testing before inserting means the answer is returned the moment a second copy appears, without finishing the scan. Time is O(n) on average, and space is O(n) in the worst case when all values are distinct.
def has_repeat(items):
seen = set() # values met so far
for x in items:
if x in seen: # this exact value already appeared
return True
seen.add(x)
return False # the scan finished without a collision
print(has_repeat([4, 1, 9, 1])) # -> True
print(has_repeat([4, 1, 9])) # -> False
print(has_repeat([])) # -> FalseStuck on the idea rather than the code? Hash Table Basics covers it.