961. N-Repeated Element in Size 2N Array

EasyArrayHash Table
Leetcode Link

Problem Description

You are provided with an integer array, nums, which has some unique properties. The length of the array is 2n, indicating that it consists of twice the quantity of a certain number n. Within this array, there are n + 1 distinct elements, meaning there are only a few unique elements. Among these unique elements, there is one particular element that appears exactly n times. The challenge here is to identify that one element which is repeated n times and return it.

Intuition

The intuition behind the solution lies in understanding the properties of the set data structure and the constraints mentioned in the problem. A set in Python is a collection that is unordered and unindexed, and most importantly, it does not allow duplicate elements. Since we know there are n repeats of the same element and only n + 1 unique elements in the array, we can iterate through the array and add each element to the set.

The moment we encounter an element that's already present in the set, we know that it must be the one that is repeated n times. This is because we can only add unique elements to the set, and trying to add a duplicate will not change the set, thus highlighting the repeat. Once we identify the repeated element, we can immediately return it, as we are guaranteed by the problem's properties that only one element is repeated n times.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution directly follows the intuition. Here's a step-by-step walk-through of the implementation, which is quite simple and efficient due to the particular constraints of the problem:

  1. A set, s, is created to keep track of the unique elements we encounter in the nums array. In Python, a set is valuable because it stores elements in an unordered fashion and, most importantly for our case, does not allow duplicates.

  2. We iterate over each element x in the array nums. For each element, we perform a check to determine whether it already exists in the set s.

  3. If x is not present in the set (which means this is the first time we're seeing this number), we add it to the set using s.add(x).

  4. If x is already in the set s, then it means we have found the duplicate element which has occurred n times, in compliance with the problem's constraints. We then immediately return x.

  5. The loop will continue until the condition in step 4 is met, which is guaranteed to happen since we know from the problem statement that one element is repeated n times.

By using the set and leveraging its properties, we avoid having to compare each element with every other element, which would be a less efficient approach. The use of a set provides a quick and concise way to detect the repeat without additional memory for counting or additional nested loops, making this algorithm run in O(n) time complexity and O(n) space complexity, where n is the number of unique elements in the array.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we are given an array nums with the following elements: [1, 2, 3, 3].

Following the step-by-step solution:

  1. First, we create an empty set s to store unique elements we encounter in the nums array. Initially, s = {}.

  2. We start iterating over each element x in the nums array.

    • On the first iteration, x = 1. Since 1 is not in the set s, we add 1 to s. Now s = {1}.
    • On the second iteration, x = 2. Since 2 is not in s, we add 2 to s. Now s = {1, 2}.
    • On the third iteration, x = 3. Since 3 is not in s, we add 3 to s. Now s = {1, 2, 3}.
    • On the fourth iteration, x = 3 again. But this time, 3 is already in s, so we have found our duplicate element.

  3. As soon as we find that 3 is already in the set s, we don't need to look any further. We immediately return 3 as the duplicate element that is repeated n (2) times.

This example showed how the algorithm efficiently traverses the array and uses a set to find the repeating element without the need for unnecessary comparisons or additional memory for counts. The implementation matches the intuition and the problem constraints, offering a simple yet powerful solution.

Solution Implementation

1from typing import List
2
3class Solution:
4    def repeatedNTimes(self, nums: List[int]) -> int:
5        """
6        Find the element that is repeated N times in the given list, where the list size is 2N.
7      
8        Args:
9        nums: List[int] - A list of integers with size 2N.
10      
11        Returns:
12        int - The integer that is repeated N times.
13        """
14      
15        seen = set()  # Initialize an empty set to keep track of seen elements.
16      
17        for num in nums:
18            if num in seen:
19                # If the number is already in the set, we have found our repeated element.
20                return num
21            # Add the current number to the set.
22            seen.add(num)
23          
24        # The function should always return within the loop for well-formed inputs.
25        # An explicit return None could be added here, but it's unnecessary.
26
1class Solution {
2    // This method finds the element that is repeated N times in the array `nums`.
3    public int repeatedNTimes(int[] nums) {
4        // Create a HashSet to store unique elements.
5        // The initial capacity is set to nums.length / 2 + 1 because we know there is
6        // one element repeating N times in a 2N sized array.
7        Set<Integer> uniqueElements = new HashSet<>(nums.length / 2 + 1);
8      
9        // Iterate through each element in the array.
10        for (int i = 0;; ++i) { // the loop will break from the inside so no condition is set here
11            // Attempt to add the current element to the HashSet.
12            // If the add() method returns false, it means the element is already in the set
13            // and hence, it is the element that repeats N times.
14            if (!uniqueElements.add(nums[i])) {
15                // Return the repeated element.
16                return nums[i];
17            }
18        }
19        // Since there must be an N times repeated element by the problem statement, the loop
20        // is guaranteed to return at some point and does not require an explicit termination condition.
21    }
22}
23
1#include <vector>
2#include <unordered_set>
3
4class Solution {
5public:
6    // Function to find the element that is repeated N times in the array
7    int repeatedNTimes(vector<int>& nums) {
8        // Create an unordered set to keep track of visited elements
9        unordered_set<int> visitedElements;
10
11        // Iterate over the array
12        for (int i = 0; i < nums.size(); ++i) {
13            // Check if the current element is already in the set
14            if (visitedElements.count(nums[i])) {
15                // If it is in the set, we've found the repeated element
16                return nums[i];
17            }
18            // If it is not in the set, add the current element to the set
19            visitedElements.insert(nums[i]);
20        }
21      
22        // If the loop completes without returning, there is a problem with the input
23        // as the problem definition guarantees a repeated element
24        // However, the return statement below is needed to avoid a compiler error.
25        return -1;
26    }
27};
28
1/**
2 * Finds the element that is repeated N times in an array where all other elements appear exactly once.
3 *
4 * @param {number[]} elements - An array of numbers which contains a unique element and one element repeated N times.
5 * @returns {number} - The number that is repeated N times.
6 */
7function repeatedNTimes(elements: number[]): number {
8    // Initialize a new Set to store unique elements as we encounter them.
9    const uniqueElements: Set<number> = new Set();
10
11    // Iterate through each number in the array.
12    for (const element of elements) {
13        // Check if the current element is already in the Set.
14        if (uniqueElements.has(element)) {
15            // If so, we have found our repeated element and return it.
16            return element;
17        }
18        // Otherwise, add the element to the Set of unique elements.
19        uniqueElements.add(element);
20    }
21  
22    // The function assumes that there will always be a repeated element,
23    // so there is no explicit return statement outside the loop.
24    // TypeScript will infer that the end of the function is unreachable code.
25    // If the input is guaranteed to always have a repeated element, this is fine. 
26    // Otherwise, you should handle the case where no element is repeated:
27    // throw new Error('No repeated element found');
28}
29
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement priority queue?

Time and Space Complexity

The given Python code aims to find an element that is repeated N times in a list where 2N elements are present, and N-1 elements are unique.

Time Complexity

The time complexity is O(N) because the function iterates through each element of the list exactly once in the worst case (where N is the length of the list).

Space Complexity

The space complexity is also O(N) as it uses a set to store elements encountered in the list. In the worst case, this set will store N-1 elements when the repeated element is the last one to be checked.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫