{x}
blog image

N-Repeated Element in Size 2N Array

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.

Solution Explanation:

This problem asks to find the element that appears n times in an array of length 2n, where n+1 elements are unique. The most efficient approach leverages a hash set (or dictionary in Python) to track seen elements.

Approach:

  1. Initialization: Create an empty hash set (or dictionary) to store the unique elements encountered so far.

  2. Iteration: Iterate through the input array nums.

  3. Check and Return: For each element x in nums:

    • If x is already present in the hash set, it means we've encountered it before. This is the repeated element, so return x.
    • If x is not in the hash set, add it to the hash set to mark it as seen.

Time and Space Complexity Analysis:

  • Time Complexity: O(n) - In the worst case, we iterate through the entire array once. Hash table lookups (checking if an element exists) and insertions are typically O(1) on average.

  • Space Complexity: O(n) - In the worst case, we might store up to n unique elements in the hash set.

Code Explanation with Examples:

The provided code implements this approach in several languages. Let's examine the Python code as an example:

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        s = set() # Initialize an empty set
        for x in nums: # Iterate through the array
            if x in s: # Check if the element is already in the set
                return x # If it is, return it (this is the repeated element)
            s.add(x) # If not, add it to the set

Example Walkthrough (Python):

Let's trace the execution for nums = [1, 2, 3, 3]:

  1. s = set() (empty set)
  2. x = 1: 1 is not in s, so s becomes {1}.
  3. x = 2: 2 is not in s, so s becomes {1, 2}.
  4. x = 3: 3 is not in s, so s becomes {1, 2, 3}.
  5. x = 3: 3 is in s, so the function immediately returns 3.

The other language implementations follow the same logic, using their respective hash set/dictionary data structures. The for loop iterates through the array once, making the time complexity linear. The space used by the hash set is proportional to the number of unique elements, which is at most n.