# N-Repeated Element in Size 2N Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/n-repeated-element-in-size-2n-array)
Canonical: https://scaleengineer.com/dsa/problems/n-repeated-element-in-size-2n-array
**Data structures:** Array, Hash Table
**Companies:** [Akamai](https://scaleengineer.com/companies/akamai)
---
## Problem
You are given an integer array `nums` with the following properties:

* `nums.length == 2 * n`.
* `nums` contains `n + 1` **unique** elements.
* Exactly one element of `nums` is repeated `n` times.

Return _the element that is repeated_ `n` _times_.

**Example 1:**

**Input:** nums = [1,2,3,3]
**Output:** 3

**Example 2:**

**Input:** nums = [2,1,2,5,3,2]
**Output:** 2

**Example 3:**

**Input:** nums = [5,1,5,2,5,3,5,4]
**Output:** 5

**Constraints:**

* `2 <= n <= 5000`
* `nums.length == 2 * n`
* `0 <= nums[i] <= 104`
* `nums` contains `n + 1` **unique** elements and one of them is repeated exactly `n` times.

# Approaches
## Brute Force with Nested Loops
This approach uses two nested loops to compare every element of the array with every other element. When a pair of identical elements is found, that element is the answer. This is the most straightforward but least efficient method.
**Time:** O(N^2) - Where N is the length of the `nums` array. For each element, we iterate through the rest of the array, leading to a quadratic number of comparisons. · **Space:** O(1) - No extra data structures are used, so the space complexity is constant.
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1).
**Cons:** Highly inefficient with a time complexity of O(N^2).; It will be very slow for large input arrays and may result in a 'Time Limit Exceeded' error on online judges.
### Explanation
The brute-force solution involves a nested iteration over the array. The outer loop selects an element, and the inner loop scans the rest of the array to find a duplicate. Because the problem guarantees that exactly one element is repeated, the first duplicate we find must be the N-repeated element.

```java
class Solution {
    public int repeatedNTimes(int[] nums) {
        int N = nums.length;
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                if (nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
- Use a nested loop structure.
- The outer loop iterates from the first element to the last, with index `i`.
- The inner loop iterates from `i + 1` to the last element, with index `j`.
- Inside the inner loop, compare `nums[i]` and `nums[j]`.
- If they are equal, `nums[i]` is the repeated element, so return it.
- Since it's guaranteed that exactly one element is repeated `n` times, this loop will always find the repeated element.

## Sorting the Array
This method involves sorting the array first. Once sorted, the `n` identical elements will be grouped together. A single pass over the sorted array can then easily find an element that is the same as its neighbor.
**Time:** O(N log N) - Where N is the length of the array. This is dominated by the time taken to sort the array. · **Space:** O(log N) to O(N) - The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitives uses a variant of Quicksort which requires O(log N) space for the recursion stack on average. Mergesort would require O(N) space.
**Pros:** Conceptually simple and easy to implement.; More efficient than the brute-force approach.
**Cons:** The time complexity is dominated by the sorting algorithm, which is generally O(N log N).; It either modifies the original array or requires O(N) space to store a copy.; The space complexity for sorting can be up to O(N) depending on the implementation.
### Explanation
By sorting the array, we ensure that all equal elements are placed next to each other. Since one element is repeated `n` times, there must be at least one pair of adjacent elements that are identical. We can then iterate through the array and check for this condition.

```java
import java.util.Arrays;

class Solution {
    public int repeatedNTimes(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; ++i) {
            if (nums[i] == nums[i+1]) {
                return nums[i];
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- After sorting, all `n` copies of the repeated element will be adjacent to each other.
- Iterate through the sorted array from the first element up to the second-to-last element.
- Compare each element `nums[i]` with the next element `nums[i+1]`.
- If `nums[i] == nums[i+1]`, you have found the repeated element. Return `nums[i]`.

## Using a Hash Set
A more efficient approach is to use a hash set to keep track of the elements we have seen. We iterate through the array, and for each element, we check if it's already in the set. If it is, we've found our repeated element. If not, we add it to the set and continue.
**Time:** O(N) - Where N is the length of the array. We iterate through the array once, and hash set operations (add, contains) take O(1) time on average. · **Space:** O(n) - In the worst-case scenario, we might have to store all `n` unique elements plus one instance of the repeated element before finding the duplicate. The size of the hash set is proportional to `n`.
**Pros:** Achieves linear time complexity, O(N), which is very efficient.; Simple to implement.
**Cons:** Requires extra space to store the seen elements, which can be up to O(n) in the worst case.
### Explanation
This approach leverages the O(1) average time complexity of hash set operations. We iterate through the array once. For each element, we try to add it to a set of seen numbers. If the element is already in the set, the `add` operation fails (or a `contains` check returns true), and we know we have found the duplicate. Since only one number is duplicated, this must be the answer.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int repeatedNTimes(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (!seen.add(num)) {
                return num;
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Initialize an empty `HashSet` to store unique elements encountered so far.
- Iterate through each number `num` in the input array `nums`.
- For each `num`, check if it is already present in the `HashSet`.
- If it is, then `num` is the repeated element. Return `num`.
- If it is not, add `num` to the `HashSet` and continue to the next element.

## Mathematical Insight with Bounded Distance Check
This optimal approach is based on a mathematical insight derived from the problem's constraints. Given that half the elements in a `2n` size array are a single repeated number, it's guaranteed that two of these repeated numbers must lie very close to each other. Specifically, the distance between two identical items will be at most 3. This allows us to find the repeated element in a single pass with constant extra space.
**Time:** O(N) - We perform a single pass through the array (or a fixed number of passes, 3, which is still O(N)). For each element, we do a constant number of comparisons. · **Space:** O(1) - This approach uses only a few variables for loops and indices, requiring constant extra space.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).
**Cons:** The underlying mathematical proof is not immediately obvious.
### Explanation
Let the repeated element be `x`. There are `n` copies of `x` and `n` other unique elements in an array of size `2n`. Let's assume for contradiction that any two copies of `x` are separated by a distance of at least 4 (i.e., there are at least 3 other elements between them). To place `n` copies of `x` this far apart, the total length of the array would need to be at least `1 (for the first x) + (n-1) * 4 = 4n - 3`. However, the array length is `2n`. The inequality `2n >= 4n - 3` simplifies to `3 >= 2n`, which is false for any `n >= 2` (as per the problem constraints). This contradiction proves that our assumption was wrong. Therefore, there must be at least one pair of `x`'s with a distance of 1, 2, or 3. We can find this pair by checking each element against its three predecessors.

```java
class Solution {
    public int repeatedNTimes(int[] nums) {
        for (int i = 2; i < nums.length; i++) {
            // Check for distance 1 or 2
            if (nums[i] == nums[i-1] || nums[i] == nums[i-2]) {
                return nums[i];
            }
        }
        // The only remaining case not covered by the loop is a pattern like [x, y, z, x]
        // which only happens for n=2. In this case, nums[0] is the answer.
        return nums[0];
    }
}
```
*A slightly more general implementation covering all distances up to 3:*
```java
class Solution {
    public int repeatedNTimes(int[] nums) {
        for (int k = 1; k <= 3; ++k) {
            for (int i = 0; i < nums.length - k; ++i) {
                if (nums[i] == nums[i+k]) {
                    return nums[i];
                }
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- The core idea is that the repeated element must have at least two of its copies close to each other.
- It can be proven that for an array with the given properties, there must be two identical elements with a distance of 1, 2, or 3.
- Iterate through the array from left to right, starting from index 1.
- For each element `nums[i]`, compare it with its immediate neighbors at `nums[i-1]`, `nums[i-2]`, and `nums[i-3]` (if they exist).
- If a match is found, return that element.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var repeatedNTimes = function ( nums ) { const s = new Set (); for ( const x of nums ) { if ( s . has ( x )) { return x ; } s . add ( x ); } };
```

### Java

```java
class Solution {
public
  int repeatedNTimes(int[] nums) {
    Set<Integer> s = new HashSet<>(nums.length / 2 + 1);
    for (int i = 0;; ++i) {
      if (!s.add(nums[i])) {
        return nums[i];
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int repeatedNTimes(vector<int> &nums) {
    unordered_set<int> s;
    for (int i = 0;; ++i) {
      if (s.count(nums[i])) {
        return nums[i];
      }
      s.insert(nums[i]);
    }
  }
};

```

### Python

```python
class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int: s = set() for x in nums: if x in s: return x s . add(x)

```