Scale Engineer

N-Repeated Element in Size 2N Array

Easy
#0915Time: 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.1 company
Data structures
ArrayHash Table
Companies
Akamai

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

/** * @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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem