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

LeetCode Problem 961

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem gives us an integer array nums whose length is exactly 2 * n. Among all the numbers in the array, there are n + 1 distinct values. One special value appears exactly n times, while every other value appears only once.

Our task is to identify and return the value that appears repeatedly.

Another way to think about the problem is this:

• The array contains one "dominant" number.
• That number occurs many times, specifically half of the total array length.
• Every other number appears exactly once.

For example, consider:

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

The array length is 6, so n = 3.

The value 2 appears 3 times, which matches n. Every other number appears once. Therefore, the answer is 2.

The constraints are relatively small:

• 2 <= n <= 5000
• Maximum array size is 10000
• Values range from 0 to 10^4

These constraints tell us that even an O(n^2) solution would technically pass because 10000^2 operations is still manageable in many environments. However, the problem is designed to encourage a more efficient solution.

An important guarantee is that there is always exactly one valid repeated element. This means we never need to handle ambiguous cases or situations where no answer exists.

Several edge cases are important to recognize early:

• The repeated element may appear consecutively, such as [3,3,1,2]
• The repeated element may be spread throughout the array, such as [5,1,5,2,5,3,5,4]
• The repeated value could be 0
• The smallest valid input size is length 4
• The repeated element may appear very early or very late in the traversal

Because the problem guarantees exactly one repeated value occurring n times, we can safely return immediately once we detect a duplicate.

Approaches

Brute Force Approach

The brute-force solution compares every element with every other element.

For each index i, we scan the remainder of the array and count how many times nums[i] appears. If its frequency becomes greater than 1, we know it is the repeated element because all other elements appear exactly once.

This approach works because the problem guarantees that only one value appears multiple times.

However, the method is inefficient because it repeatedly scans the array. With nested loops, the total time complexity becomes quadratic.

Key Insight for the Optimal Solution

The critical observation is that we do not actually need to count frequencies completely.

Since all non-repeated values appear exactly once, the first value we encounter twice must be the repeated element.

This naturally suggests using a hash set:

• Traverse the array from left to right
• Store each previously seen number in a set
• If the current number already exists in the set, return it immediately

Hash sets provide average O(1) lookup time, making the entire algorithm linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare each element against all others
Optimal	O(n)	O(n)	Use a hash set to detect the first duplicate

Algorithm Walkthrough

1. Create an empty hash set called seen.

The set will store all numbers we have already processed. A hash set is ideal because membership checks are extremely fast on average. 2. Iterate through each number in nums.

We process the array one element at a time. 3. For the current number, check whether it already exists in seen.

• If it does, we have found the repeated element.
• Return it immediately.

This works because every non-repeated number appears exactly once. 4. If the number is not already in the set, insert it into seen.

This records that we have now encountered the value. 5. Continue until a duplicate is found.

The problem guarantees that exactly one element repeats n times, so the algorithm will always return a value.

Why it works

The correctness depends on the problem guarantee that every value except one appears exactly once.

As we iterate through the array:

• The first occurrence of a number is added to the set
• Any second occurrence must belong to the repeated element, because no other value can appear more than once

Therefore, the first duplicate encountered is guaranteed to be the correct answer.

Python Solution

from typing import List

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

        for number in nums:
            if number in seen:
                return number

            seen.add(number)

        return -1

The implementation begins by creating an empty set named seen. This set tracks every value encountered during traversal.

The for loop processes each number in the array exactly once. Before inserting a number into the set, the algorithm checks whether it already exists.

If the value is already present, that means we have encountered the repeated element, so the function immediately returns it.

Otherwise, the number is added to the set and traversal continues.

The final return -1 statement is technically unnecessary because the problem guarantees a valid answer, but it satisfies Python's requirement that all execution paths return a value.

Go Solution

func repeatedNTimes(nums []int) int {
    seen := make(map[int]bool)

    for _, number := range nums {
        if seen[number] {
            return number
        }

        seen[number] = true
    }

    return -1
}

The Go solution follows the same logic as the Python implementation.

Since Go does not have a built-in set type, we simulate one using map[int]bool. The map keys represent values we have already seen.

During iteration:

• If seen[number] is already true, we return the duplicate
• Otherwise, we store the number in the map

There are no integer overflow concerns because the constraints are very small. The solution also works correctly for empty-like edge behavior, although the problem guarantees a valid non-empty input.

Worked Examples

Example 1

nums = [1,2,3,3]

Step	Current Number	Seen Set	Action
1	1	{}	Add 1
2	2	{1}	Add 2
3	3	{1,2}	Add 3
4	3	{1,2,3}	Duplicate found, return 3

Result:

3

Example 2

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

Step	Current Number	Seen Set	Action
1	2	{}	Add 2
2	1	{2}	Add 1
3	2	{1,2}	Duplicate found, return 2

Result:

2

Example 3

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

Step	Current Number	Seen Set	Action
1	5	{}	Add 5
2	1	{5}	Add 1
3	5	{1,5}	Duplicate found, return 5

Result:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once
Space	O(n)	The hash set may store up to n unique values

The algorithm performs a single linear scan through the array. Each hash set lookup and insertion operation takes average constant time.

In the worst case, the set stores all unique elements before encountering the duplicate, which requires linear auxiliary space.

Test Cases

from typing import List

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

        for number in nums:
            if number in seen:
                return number

            seen.add(number)

        return -1

solution = Solution()

assert solution.repeatedNTimes([1,2,3,3]) == 3  # basic example
assert solution.repeatedNTimes([2,1,2,5,3,2]) == 2  # repeated element spread out
assert solution.repeatedNTimes([5,1,5,2,5,3,5,4]) == 5  # repeated many times

assert solution.repeatedNTimes([0,0,1,2]) == 0  # repeated value is zero
assert solution.repeatedNTimes([9,5,9,1]) == 9  # duplicate appears early
assert solution.repeatedNTimes([1,2,3,4,4,4,4,5]) == 4  # repeated element clustered

assert solution.repeatedNTimes([7,7,1,2]) == 7  # duplicate at beginning
assert solution.repeatedNTimes([1,2,3,4,5,6,6,6,6,6]) == 6  # larger repetition count
assert solution.repeatedNTimes([8,1,2,3,8,4,5,6,8,7]) == 8  # repeated element distributed

Test Summary

Test	Why
[1,2,3,3]	Smallest standard example
[2,1,2,5,3,2]	Repeated element appears multiple times non-consecutively
[5,1,5,2,5,3,5,4]	Larger array with interleaved duplicates
[0,0,1,2]	Ensures zero is handled correctly
[9,5,9,1]	Duplicate detected early
[1,2,3,4,4,4,4,5]	Consecutive repeated values
[7,7,1,2]	Duplicate at the start
[1,2,3,4,5,6,6,6,6,6]	Higher repetition count
[8,1,2,3,8,4,5,6,8,7]	Duplicate spread across the array

Edge Cases

One important edge case is the minimum input size. The smallest valid array has length 4, meaning n = 2. For example:

[1,2,2,3]

A buggy implementation might incorrectly assume larger input sizes or rely on multiple duplicate encounters. The hash set approach works immediately because it only needs a single repeated occurrence to identify the answer.

Another important edge case occurs when the repeated value is 0. Some implementations accidentally treat 0 as a special falsy value or fail to store it correctly in maps or sets. Since the algorithm uses standard hash set membership checks, 0 is handled exactly like any other integer.

A third edge case is when the repeated element appears consecutively at the beginning of the array, such as:

[7,7,1,2]

Some algorithms that rely on spacing patterns or delayed detection may fail here. The hash set solution correctly detects the duplicate on the second iteration and returns immediately.

Another subtle case occurs when the repeated element is distributed throughout the array rather than clustered together. For example:

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

The implementation does not rely on adjacency. It only relies on whether a value has been seen before, so distribution patterns do not affect correctness.