Teaching Kids Programming – N-Repeated Element in Size 2N Array (Hash Map/Set)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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^4
nums contains n + 1 unique elements and one of them is repeated exactly n times.

N-Repeated Element in Size 2N Array (Hash Map/Set)

The given array only has an element which appears more than once (N times), thus, we can simply use a hash set to return the first element that appears more than once. This takes O(N) time and space.

1
2
3
4
5
6
7

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        c = set()
        for i in nums:
            if i in c:
                return i
            c.add(i)

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        c = set()
        for i in nums:
            if i in c:
                return i
            c.add(i)

We can use the Counter which counts the frequencies of the elements and store them in the hash table, and then we can go through the hash table or the elements to find out which number appears N times or appears more than once. This solution has O(N) time and space, but it needs to traverse the array twice, so it is less efficient than the first approach.

1
2
3
4
5
6

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        c = Counter(nums)
        for i in c:
            if c[i] == len(nums):  ## or simple check c[i] > 1
                return i

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        c = Counter(nums)
        for i in c:
            if c[i] == len(nums):  ## or simple check c[i] > 1
                return i

N-Repeated Element in Size 2N Array

• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Pigeonhole Principle)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Random Algorithm)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Math)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Sorting)
• Teaching Kids Programming - N-Repeated Element in Size 2N Array (Hash Map/Set)
• Algorithms: How to Find N-Repeated Element in Size 2N Array?

–EOF (The Ultimate Computing & Technology Blog) —