Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The input guarantees that exactly one value repeats and all other values occur once. Consequently, the first duplicate encountered must be the required value; its full frequency need not be counted.

Approach

Scan the array while keeping a set of previously encountered values. Before adding a value, return it if it is already in the set. Otherwise add it and continue. The guaranteed repeated element ensures the scan returns an answer, and the membership test is performed before insertion so a first occurrence is never mistaken for a duplicate.

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        seen = set()

        for x in nums:
            if x in seen:
                return x
            seen.add(x)

Complexity analysis

For n = nums.length, the set scan takes O(n) expected time and O(n) auxiliary space in the worst case.