N-Repeated Element in Size 2N Array

EASY

Description

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] <= 10⁴
nums contains n + 1 unique elements and one of them is repeated exactly n times.

Approaches

Checkout 4 different approaches to solve N-Repeated Element in Size 2N Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(1) - No extra data structures are used, so the space complexity is constant.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for N-Repeated Element in Size 2N Array. Click on different languages to view the code.

/** * @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 ); } };

Video Solution

Watch the video walkthrough for N-Repeated Element in Size 2N Array

Data Structures:

ArrayHash Table

Companies:

Akamai |