Teaching Kids Programming – N-Repeated Element in Size 2N Array (Sorting)

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 (Sorting)

By sorting, we can compare neighbouring numbers (compare current number with next or previous number) and return the duplicate number if we find any.

1
2
3
4
5
6
7

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return nums[i]
        return -1

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return nums[i]
        return -1

Using the next function to achieve online:

1
2

nums.sort()
return next((nums[i] for i in range(1, len(nums)) if nums[i] == nums[i - 1]), -1)

nums.sort()
return next((nums[i] for i in range(1, len(nums)) if nums[i] == nums[i - 1]), -1)

The time complexity is O(NLogN).

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) —