LeetCode 961: N-Repeated Element in Size 2N Array

Problem Restatement

We are given an integer array nums.

The array has these properties:

Return the value that appears n times.

The official constraints include 2 <= n <= 5000, nums.length == 2 * n, and 0 <= nums[i] <= 10^4.

Input and Output

Example function shape:

def repeatedNTimes(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 2, 3, 3]

Output:

3

Here n = 2, because the array length is 4.

The value 3 appears 2 times.

Example 2:

nums = [2, 1, 2, 5, 3, 2]

Output:

2

Here n = 3, because the array length is 6.

The value 2 appears 3 times.

Example 3:

nums = [5, 1, 5, 2, 5, 3, 5, 4]

Output:

5

Here n = 4, because the array length is 8.

The value 5 appears 4 times.

First Thought: Count Every Number

A direct solution is to count how many times each value appears.

Then return the value whose count is greater than 1.

Example:

nums = [2, 1, 2, 5, 3, 2]

The counts are:

2 -> 3
1 -> 1
5 -> 1
3 -> 1

So the answer is 2.

This works, but we do not need full counts. The problem guarantee gives us a simpler approach.

Key Insight

Only one value appears more than once.

All other values appear exactly once.

So the first duplicate we see must be the answer.

We can scan the array and store values we have already seen.

When we see a value that is already in the set, return it immediately.

Algorithm

Create an empty set called seen.

For each number x in nums:

1. If x is already in seen, return x.
2. Otherwise, add x to seen.

Because the repeated value appears n times, we are guaranteed to find it.

Correctness

The array contains exactly one value that appears n times. Every other value appears exactly once.

The algorithm scans the array from left to right and stores every value it has already seen.

If the algorithm finds a value already in seen, then that value has appeared before. Therefore, it appears at least twice.

Since all non-answer values appear exactly once, this repeated value cannot be any non-answer value. It must be the element repeated n times.

Because the repeated element appears multiple times, the scan will eventually encounter it after its first occurrence. At that moment, the algorithm returns it.

Therefore, the algorithm always returns exactly the required element.

Complexity

Let m = len(nums).

Since m = 2n, this is also O(n) time and O(n) space.

Implementation

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

        for x in nums:
            if x in seen:
                return x

            seen.add(x)

        return -1

Code Explanation

We create a set:

seen = set()

This lets us check quickly whether a number appeared earlier.

For each number:

for x in nums:

we check whether it has already appeared:

if x in seen:
    return x

If yes, this value must be the repeated element.

Otherwise, we record it:

seen.add(x)

The final return is only a safety fallback:

return -1

For valid LeetCode input, it will not be reached.

Testing

def run_tests():
    s = Solution()

    assert s.repeatedNTimes([1, 2, 3, 3]) == 3
    assert s.repeatedNTimes([2, 1, 2, 5, 3, 2]) == 2
    assert s.repeatedNTimes([5, 1, 5, 2, 5, 3, 5, 4]) == 5

    assert s.repeatedNTimes([9, 9]) == 9
    assert s.repeatedNTimes([4, 1, 4, 2, 4, 3]) == 4
    assert s.repeatedNTimes([0, 1, 2, 0]) == 0

    print("all tests passed")

run_tests()

Test meaning: