Jobs

Interviews

Discussions

N-Repeated Element in Size 2N Array

Easy

Asked by:

5 views

Topics:

Arrays

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.

Try coding it in LeetCode

N-Repeated Element in Size 2N Array

Easy

Asked by:

5 views

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the array length always exactly twice some positive integer N?
Is there exactly one value that appears N times, with every other value appearing once?
Can the values be negative or zero?
Should the function return the repeated value itself, rather than an index?
Will the array always contain at least two elements?

Brute Force Solution

Approach

Compare every pair of positions until two of them hold the same value. Every other value appears only once, so the first match is the value repeated N times. Return that value as soon as the match is found.

Here's how the algorithm would work step-by-step:

Start at the beginning of the array and pick one position.
Compare that value with each position that comes after it.
When two different positions hold the same value, that value is the repeated one.
Return it immediately, without scanning the rest of the array.
The problem promises this value exists, so a match is always found.

Code Implementation

def repeatedNTimes(numbers):
    # This outer loop selects an element to compare against all subsequent elements.
    for first_pointer_index in range(len(numbers)):

        # This inner loop checks every element after the one selected by the outer loop.
        for second_pointer_index in range(first_pointer_index + 1, len(numbers)):

            # If two distinct elements at different indices are identical, we have found the repeated number.
            if numbers[first_pointer_index] == numbers[second_pointer_index]:
                return numbers[first_pointer_index]

Big(O) Analysis

Time Complexity

O(n^2) – In the worst case the matching pair sits near the end, so nearly every pair of positions is compared. Each comparison is a single equality check. The number of pairs grows with the square of the array length. The scan stops at the first match, but that match can still be the last pair. No second pass is required after the value is found.

Space Complexity

O(1) – Only the two positions being compared are remembered. The array is read in place and is not copied. No frequency table is built. Extra memory stays constant no matter how long the array is.

Optimal Solution

Approach

Remember each value the first time it appears. The moment a value shows up that was already remembered, it is the one repeated N times, because every other value appears only once. Return that value and stop.

Here's how the algorithm would work step-by-step:

Start with an empty memory of values already seen.
Walk the array from left to right.
If the current value is already remembered, return it.
Otherwise remember it and keep going.
The first repeated value encountered is the answer.

Code Implementation

def repeated_n_times(numbers_list):
    # This collection will store the unique numbers we have encountered.
    seen_numbers = set()

    for current_number in numbers_list:
        # Check if the number is already in our collection of seen numbers.
        if current_number in seen_numbers:
            # If we find a number we've already seen, it must be the one repeated N times.
            return current_number
        
        # If this is the first time seeing the number, add it to our collection.
        seen_numbers.add(current_number)

Big(O) Analysis

Time Complexity

O(n) – Each element is visited once. Checking whether a value was seen, and remembering it, takes constant time on average. The scan stops at the first repeat, which is never later than the end of the array. Total work grows in proportion to the length of the array. There is no nested search over later positions.

Space Complexity

O(n) – Every unique value may need to be remembered before the repeat appears. In the worst case that is about half of the array, which still grows with the length. The original array is not copied. Memory is dominated by the set of values already seen.

Edge Cases

Case	How to Handle
The array holds two identical numbers	Both positions hold the repeated value, so that value is returned.
The repeated value is zero	Zero is a real value and is returned when it is seen again.
The repeated value is negative	Equality still identifies the repeated value, so the sign does not change the result.
The copies are not next to each other	The search compares later positions as well, so a distant copy is still found.
Many unique values come before the repeat	Those unique values are passed over until the value that occurs again is reached.

The array holds two identical numbers

How to Handle:

Both positions hold the repeated value, so that value is returned.

The repeated value is zero

How to Handle:

Zero is a real value and is returned when it is seen again.

The repeated value is negative

How to Handle:

Equality still identifies the repeated value, so the sign does not change the result.

The copies are not next to each other

How to Handle:

The search compares later positions as well, so a distant copy is still found.

Many unique values come before the repeat

How to Handle:

Those unique values are passed over until the value that occurs again is reached.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the array length always exactly twice some positive integer N?
Is there exactly one value that appears N times, with every other value appearing once?
Can the values be negative or zero?
Should the function return the repeated value itself, rather than an index?
Will the array always contain at least two elements?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the array and pick one position.
Compare that value with each position that comes after it.
When two different positions hold the same value, that value is the repeated one.
Return it immediately, without scanning the rest of the array.
The problem promises this value exists, so a match is always found.

Code Implementation

def repeatedNTimes(numbers):
    # This outer loop selects an element to compare against all subsequent elements.
    for first_pointer_index in range(len(numbers)):

        # This inner loop checks every element after the one selected by the outer loop.
        for second_pointer_index in range(first_pointer_index + 1, len(numbers)):

            # If two distinct elements at different indices are identical, we have found the repeated number.
            if numbers[first_pointer_index] == numbers[second_pointer_index]:
                return numbers[first_pointer_index]

Big(O) Analysis

Time Complexity

Space Complexity

O(1) – Only the two positions being compared are remembered. The array is read in place and is not copied. No frequency table is built. Extra memory stays constant no matter how long the array is.

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an empty memory of values already seen.
Walk the array from left to right.
If the current value is already remembered, return it.
Otherwise remember it and keep going.
The first repeated value encountered is the answer.

Code Implementation

def repeated_n_times(numbers_list):
    # This collection will store the unique numbers we have encountered.
    seen_numbers = set()

    for current_number in numbers_list:
        # Check if the number is already in our collection of seen numbers.
        if current_number in seen_numbers:
            # If we find a number we've already seen, it must be the one repeated N times.
            return current_number
        
        # If this is the first time seeing the number, add it to our collection.
        seen_numbers.add(current_number)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
The array holds two identical numbers	Both positions hold the repeated value, so that value is returned.
The repeated value is zero	Zero is a real value and is returned when it is seen again.
The repeated value is negative	Equality still identifies the repeated value, so the sign does not change the result.
The copies are not next to each other	The search compares later positions as well, so a distant copy is still found.
Many unique values come before the repeat	Those unique values are passed over until the value that occurs again is reached.

The array holds two identical numbers

How to Handle:

Both positions hold the repeated value, so that value is returned.

The repeated value is zero

How to Handle:

Zero is a real value and is returned when it is seen again.

The repeated value is negative

How to Handle:

Equality still identifies the repeated value, so the sign does not change the result.

The copies are not next to each other

How to Handle:

The search compares later positions as well, so a distant copy is still found.

Many unique values come before the repeat

How to Handle:

Those unique values are passed over until the value that occurs again is reached.