N-Repeated Element in Size 2N Array

Difficulty: Easy | Acceptance: 79.90% | Paid: No Topics: Array, Hash Table

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.

Table of Contents

• Examples
• Constraints
• Hash Map (Frequency Count)
• Compare with Previous Elements

Examples

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
One element of nums is repeated n times

Hash Map (Frequency Count)

Intuition We can iterate through the array and store the frequency of each number in a hash map. The first number we encounter that already exists in the map is the repeated element.

Steps

• Initialize an empty hash map (or set).
• Iterate through each number in the array.
• If the number is already in the map, return it immediately.
• Otherwise, add the number to the map.

class Solution:
    def repeatedNTimes(self, nums: list[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)
        return -1

Complexity

• Time: O(N)
• Space: O(N)
• Notes: We use O(N) space to store the seen elements.

Compare with Previous Elements

Intuition Since the array length is 2N and one element appears N times, the repeated element must appear close to itself. Specifically, there must be at least one instance where the repeated element is within 2 indices of another instance (e.g., at positions i and i+1, or i and i+2). We can check the current element against the previous two elements.

Steps

• Iterate through the array starting from index 2.
• Check if nums[i] is equal to nums[i-1] or nums[i-2].
• If a match is found, return that number.
• Also handle the edge cases for the first few elements (indices 0, 1, 2) by checking them against each other.

class Solution:
    def repeatedNTimes(self, nums: list[int]) -> int:
        n = len(nums)
        # Check the first few elements manually to cover all bases
        if nums[0] == nums[1] or nums[0] == nums[2]:
            return nums[0]
        if nums[1] == nums[2]:
            return nums[1]
            
        # Check the rest of the array
        for i in range(3, n):
            if nums[i] == nums[i-1] or nums[i] == nums[i-2]:
                return nums[i]
        return -1

Complexity

• Time: O(N)
• Space: O(1)
• Notes: This approach is optimal in terms of space complexity as it only uses a constant amount of extra memory.