🎯 Beginner-Friendly Guide 'N-Repeated Element in Size 2N Array' – LeetCode 961 (C++ | Python | JavaScript)

Source: Dev.to

Problem Description

You are given an array nums of length 2N.
The array contains N + 1 unique elements, and exactly one of those elements appears N times.

Goal: Identify and return the element that is repeated N times.

Solution Overview

Because the repeated element occupies half of the array positions, two occurrences of it must be at most two indices apart.
Scanning the array with a sliding window of size 3 guarantees that we will encounter a duplicate unless the repeated element is the last array entry.

The algorithm runs in O(N) time and uses O(1) extra space.

C++ Implementation

class Solution {
public:
    int repeatedNTimes(vector& nums) {
        // Check windows of size 2 and size 3
        for (int i = 0; i + 2  int:

Python Implementation

# Iterate through the list looking at neighbors
for i in range(len(nums) - 2):
    if nums[i] == nums[i + 1] or nums[i] == nums[i + 2]:
        return nums[i]

# If the repeat isn't within a distance of 2, it's the last element
return nums[-1]

JavaScript Implementation

/**
 * @param {number[]} nums
 * @return {number}
 */
var repeatedNTimes = function(nums) {
    // Loop through the array checking nearby elements
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] === nums[i + 1] || nums[i] === nums[i + 2]) {
            return nums[i];
        }
    }

    // Return the last element if no match was found in the loop
    return nums[nums.length - 1];
};

Key Insights

• Window Strategy: Checking only the immediate neighbors (distance ≤ 2) is sufficient to locate the repeated element in a 2N array.
• Space Efficiency: The algorithm uses O(1) extra space, far better than the O(N) space required by a frequency counter.
• Logic Over Brute Force: Understanding the pigeonhole principle behind the element distribution leads to a simple, fast solution.