N-Repeated Element in Size 2N Array: Finding the Majority with a Set

LeetCode N-Repeated Element in Size 2N Array (problem 961) gives you an array of length 2n that contains n + 1 unique values. Exactly one of those values is repeated, and it appears exactly n times. Your job is to find and return that repeated element.

For example, given nums = [1, 2, 3, 3], the array has length 4 (so n = 2). There are 3 unique values, and the value 3 appears twice. Return 3.

Why this problem is interesting

At first glance, this looks like a simple counting problem. And it is. But the structure of the input gives you a powerful shortcut that most people overlook.

Think about it: the array has 2n slots. One value occupies n of them. That leaves n slots for the other n unique values, meaning each of those other values appears exactly once. So the repeated element is the only value that appears more than once. You do not need to count to n. You just need to find the first duplicate.

The key insight: pigeonhole collision

Since n + 1 unique values must fill 2n slots, and n of those slots belong to a single value, the repeated element must collide with itself quickly. By the pigeonhole principle, if you scan the array and track what you have already seen, the repeated element will show up a second time within the first n + 1 elements at most.

A simple hash set makes this fast. Walk through the array, check if the current value is already in the set, and return it the moment you find a match.

The set-based solution

def repeatedNTimes(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)

That is the entire solution. One pass, one set, one check per element.

Each in check on a set is O(1) on average. Each add is O(1). You stop as soon as you find the duplicate. In the worst case, you scan n + 1 elements before finding it.

Step-by-step walkthrough

Let's trace through nums = [5, 1, 5, 2, 5, 3, 5, 4]. Here n = 4, so the array has 8 elements, and the repeated value (5) appears 4 times.

The algorithm finds the duplicate after just three steps. It never needs to look at the rest of the array. The set catches the collision immediately.

Why not just count frequencies?

You could use a Counter or dictionary to count every element and then find the one with count n. That works, but it is overkill. You do not need to count anything. The problem guarantees exactly one repeated element, so the first duplicate you encounter is the answer.

The set approach is simpler, uses less memory in practice (you stop early), and avoids the extra pass to scan the frequency dictionary.

from collections import Counter

def repeatedNTimes_counter(nums):
    n = len(nums) // 2
    counts = Counter(nums)
    for val, cnt in counts.items():
        if cnt == n:
            return val

This works, but it processes the entire array before returning. The set approach returns the moment it finds the duplicate.

Complexity analysis

The time complexity is technically O(n) in the worst case, but in practice you often stop much sooner. Since the repeated element takes up half the array, the expected number of elements you scan before finding a duplicate is small.

Building blocks

This problem uses one core reusable piece that CodeBricks drills independently:

Seen-set duplicate detection

The pattern of maintaining a set that grows as you process elements, checking membership before each insertion. If the element is already present, you have found a duplicate.

seen = set()
for item in collection:
    if item in seen:
        return item
    seen.add(item)

This same pattern appears across many problems:

• Contains Duplicate: check if any value appears twice
• Happy Number: detect cycles in the digit-squaring sequence
• Linked List Cycle: track visited nodes (though Floyd's algorithm is better)
• Longest Substring Without Repeating Characters: track characters in the current window

The skeleton is always the same: initialize an empty set, loop through items, check before inserting. The only thing that changes is what you do when you find a match.

Edge cases

Before submitting, make sure your solution handles these:

• Minimum size [1, 1]: n = 1, array has 2 elements. The repeated element is found immediately at index 1.
• Repeated element at the end [1, 2, 3, 2]: the duplicate is not adjacent, but the set catches it at index 3.
• All repeated elements grouped together [3, 3, 1, 2]: the set finds the duplicate at index 1, right away.
• Large n with interleaved repeats [5, 1, 5, 2, 5, 3, 5, 4]: the repeated element is spread across the array. The set still catches it on its second appearance.

The set-based approach handles all of these identically. No special-case logic needed.

From understanding to recall

You have read the set-based solution and it makes sense. One set, one loop, check before insert. But can you write it from scratch in an interview without looking at it?

The details matter: initializing the set, checking if x in seen before seen.add(x), and returning immediately when a match is found. These are small but critical, and easy to mix up under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the seen-set detection loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "find the duplicate" and the code flows out without hesitation.

The seen-set pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Contains Duplicate - The simplest set-based duplicate detection problem, using the exact same seen-set pattern
• Majority Element - Finding the dominant element in an array, with both hash map and Boyer-Moore approaches
• Find the Duplicate Number - A harder duplicate problem that can be solved with cycle detection instead of a set

CodeBricks breaks the N-Repeated Element problem into its seen-set duplicate detection building block, then drills it independently with spaced repetition. You type the pattern from scratch until it is automatic. When a duplicate detection question shows up in your interview, you do not think about it. You just write it.