LeetCode 0961. N-Repeated Element in Size 2N Array Solution in Java, C++, Python & More | Explanation + Code

Description

You are given an integer array nums with the following properties:

• nums.length == 2 * n.
• nums contains n + 1 unique values, n of which occur exactly once in the array.
• 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.

Solutions

Solution 1: Hash Table

Since the array nums has a total of 2n elements, with n + 1 distinct elements, and one element repeated n times, this means the remaining n elements in the array are all distinct.

Therefore, we only need to iterate through the array nums and use a hash table s to record the elements we've encountered. When we encounter an element x, if x already exists in the hash table s, it means x is the repeated element, and we can directly return x.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.

PythonJavaC++GoTypeScriptJavaScript

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

class Solution { public int repeatedNTimes(int[] nums) { Set<Integer> s = new HashSet<>(nums.length / 2 + 1); for (int i = 0;; ++i) { if (!s.add(nums[i])) { return nums[i]; } } } }(code-box)

class Solution { public: int repeatedNTimes(vector<int>& nums) { unordered_set<int> s; for (int i = 0;; ++i) { if (s.count(nums[i])) { return nums[i]; } s.insert(nums[i]); } } };(code-box)

func repeatedNTimes(nums []int) int { s := map[int]bool{} for i := 0; ; i++ { if s[nums[i]] { return nums[i] } s[nums[i]] = true } }(code-box)

function repeatedNTimes(nums: number[]): number { const s: Set<number> = new Set(); for (const x of nums) { if (s.has(x)) { return x; } s.add(x); } }(code-box)

/** * @param {number[]} nums * @return {number} */ var repeatedNTimes = function (nums) { const s = new Set(); for (const x of nums) { if (s.has(x)) { return x; } s.add(x); } };(code-box)

Solution 2: Mathematics

According to the problem description, half of the elements in the array nums are the same. If we view the array as a circular arrangement, then there is at most 1 other element between two identical elements.

Therefore, we iterate through the array nums starting from index 2. For each index i, we compare nums[i] with nums[i - 1] and nums[i - 2]. If they are equal, we return that value.

If we don't find the repeated element in the above process, then the repeated element must be nums[0], and we can directly return nums[0].

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScriptJavaScript

class Solution: def repeatedNTimes(self, nums: List[int]) -> int: for i in range(2, len(nums)): if nums[i] == nums[i - 1] or nums[i] == nums[i - 2]: return nums[i] return nums[0](code-box)

class Solution { public int repeatedNTimes(int[] nums) { for (int i = 2; i < nums.length; ++i) { if (nums[i] == nums[i - 1] || nums[i] == nums[i - 2]) { return nums[i]; } } return nums[0]; } }(code-box)

class Solution { public: int repeatedNTimes(vector<int>& nums) { for (int i = 2; i < nums.size(); ++i) { if (nums[i] == nums[i - 1] || nums[i] == nums[i - 2]) { return nums[i]; } } return nums[0]; } };(code-box)

func repeatedNTimes(nums []int) int { for i := 2; i < len(nums); i++ { if nums[i] == nums[i-1] || nums[i] == nums[i-2] { return nums[i] } } return nums[0] }(code-box)

function repeatedNTimes(nums: number[]): number { for (let i = 2; i < nums.length; ++i) { if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) { return nums[i]; } } return nums[0]; }(code-box)

/** * @param {number[]} nums * @return {number} */ var repeatedNTimes = function (nums) { for (let i = 2; i < nums.length; ++i) { if (nums[i] === nums[i - 1] || nums[i] === nums[i - 2]) { return nums[i]; } } return nums[0]; };(code-box)