Module 02 · Hash Maps, Sets, and Frequency State

012. First Repeated Value

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the first integer encountered for a second time while scanning left to right. Return None if all values are distinct. This asks for the earliest repeated encounter, not the earliest first occurrence of any eventually duplicated value.

Examples

Example 1

first_repeat([3, 1, 4, 1, 5, 3])
=> 1

Although 3 appears earlier initially, 1 repeats sooner.

Example 2

first_repeat([])
=> None

No encounter exists.

Example 3

first_repeat([0, 0])
=> 0

Zero is a valid repeated value, distinct from None.

Reveal the worked solution and reasoning

Why this mechanism works

The decision depends only on whether the incoming value has appeared, not on its count or position. A set is therefore enough. Once a repeated encounter is found, later input cannot improve its encounter order.

State and boundaries

seen is the set of all values strictly before the current position.

Protocol

Start an empty set.
Query membership before insertion.
Return the value on a hit.
Add a new value and continue.
Return None if the scan ends.

Visualization

3, 1, 4 | 1, 5, 3
seen={3,1,4}
            ^ first repeated encounter

Python implementation

def first_repeat(nums):
    seen = set()
    for value in nums:
        if value in seen:
            return value
        seen.add(value)
    return None

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

first_repeat([3, 1, 4, 1, 5, 3])

L2 first_repeat: seen = set()
nums=[3, 1, 4, 1, 5, 3]; seen=set()

L3 first_repeat: for value in nums:
nums=[3, 1, 4, 1, 5, 3]; seen=set(); value=3

L6 first_repeat: seen.add(value)
nums=[3, 1, 4, 1, 5, 3]; seen={3}; value=3

L3 first_repeat: for value in nums:
nums=[3, 1, 4, 1, 5, 3]; seen={3}; value=1

L6 first_repeat: seen.add(value)
nums=[3, 1, 4, 1, 5, 3]; seen={1, 3}; value=1

L3 first_repeat: for value in nums:
nums=[3, 1, 4, 1, 5, 3]; seen={1, 3}; value=4

L6 first_repeat: seen.add(value)
nums=[3, 1, 4, 1, 5, 3]; seen={1, 3, 4}; value=4

L3 first_repeat: for value in nums:
nums=[3, 1, 4, 1, 5, 3]; seen={1, 3, 4}; value=1

Result: 1. Although 3 appears earlier initially, 1 repeats sooner.

first_repeat([])

L2 first_repeat: seen = set()
nums=[]; seen=set()

Result: None. No encounter exists.

Why the solution is correct

The set is initially correct for an empty prefix. Inserting each new value preserves its meaning. A hit proves an earlier occurrence, and all earlier encounters were misses, establishing firstness.

Time and space

O(n) expected time and O(n) auxiliary space.

Common mistakes

Sorting loses encounter order. Testing after insertion makes every value look repeated.

Reasoning card

State: seen is the set of all values strictly before the current position.

Invariant: seen contains exactly the previously processed values.

Decision to rehearse: Check membership before adding.

Finish: Return None if the scan ends

Transfer exercise

Return the earliest first occurrence among duplicated values. Explain why this requires information about the future.