Is N-Repeated Element in Size 2N Array easy or hard?

This problem is classified as Easy. The main concept is recognizing duplicate detection using hashing or sorting, which are foundational techniques in array and hash table problems.

N-Repeated Element in Size 2N Array Python/Java solution

In Python, a set is typically used to track seen elements during a single pass through the array. In Java, a HashSet or HashMap provides the same functionality. Both implementations achieve O(n) time complexity with O(n) additional space.

How to solve N-Repeated Element in Size 2N Array in O(n)?

Use a HashSet while scanning the array. Insert each element as you iterate; if the element already exists in the set, return it immediately. Since hash lookups and insertions are O(1) on average, the entire algorithm runs in linear time.

What is the best approach for N-Repeated Element in Size 2N Array?

The hash set approach is the most efficient solution. Iterate through the array and store elements in a set. If an element already exists in the set, it is the repeated element. This method runs in O(n) time with O(n) space.

Is N-Repeated Element in Size 2N Array asked at Google/Amazon/Meta?

This problem is commonly used in technical interviews as a basic array and hash table exercise. Similar duplicate-detection patterns appear in interviews at companies like Amazon, Google, and Meta to test understanding of hashing and frequency counting.

What data structure is used in N-Repeated Element in Size 2N Array?

The most common data structure used is a hash set or hash map. It allows constant-time checks to determine whether an element has already appeared while scanning the array.

What is the time complexity of N-Repeated Element in Size 2N Array?

The optimal hash table solution runs in O(n) time because each element is processed once with constant-time hash lookups. A sorting-based approach requires O(n log n) time due to the sorting step.

Description Solution Video 24:19

961. N-Repeated Element in Size 2N Array

Easy79.9% acceptance6 companies

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.

Asked at 6 companies

Akamai Zoho

Google Bloomberg Amazon Meta

Topics

Array Hash Table

24:19

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def repeatedNTimes(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,3,3]

Input

[2,1,2,5,3,2]

Input

[5,1,5,2,5,3,5,4]

Your code is saved on this device.Solution