2965. Find Missing and Repeated Values

EasyArrayHash TableMathMatrix
Leetcode Link

Problem Description

In this problem, we are presented with an n * n 2D integer matrix called grid. Within this matrix, every number from 1 to n^2 is supposed to appear exactly once, representing a perfect sequence with no repetitions and no missing numbers. However, there is a twist: one number, a, appears twice, while another number, b, does not appear at all—it's missing. This means that in the entire grid, there is precisely one number that's duplicated and another that's completely absent.

The challenge is to identify these two numbers: the one that occurred redundantly (a) and the one that's nowhere to be found (b). We are asked to return these two numbers in the form of a 0-indexed integer array of size 2, where the first element is the repeating number a and the second element is the missing number b.

Intuition

To solve this problem, we leverage a very straightforward approach which is to use counting to keep track of the occurrences of each number within the matrix.

Here's the process in simple steps:

  1. Since the numbers range from 1 to n^2, we create a counting array cnt of size n^2 + 1 so that we have a dedicated spot to store the count of each number that should ideally be present in the matrix. By using a 0-indexed array where cnt[i] is meant to store the count for the number i, we reserve the count of number i at the index i.

  2. Next, we traverse through the entire grid, row by row and column by column, and increment the count in the cnt array for each number v that we encounter along the way. The entry at cnt[v] serves as a counter for how many times the number v has appeared in the grid.

  3. After completing the count for all numbers, we check the cnt array for irregularities. There are two specific anomalies we are interested in: a doubled count (which indicates a number has appeared twice) and a zero count (which indicates a missing number). So for each index i from 1 to n^2, we check the counters: if cnt[i] equals 2, it means that i is the repeating number a and we assign i to the first element of the solution array. Conversely, if cnt[i] equals 0, it means that i is the missing number b, and we accordingly assign i to the second element of the solution array.

My reasoning behind this simple approach is that since each number should only appear once, any deviation from this pattern can be easily detected by its frequency counter. This method allows us to find both a and b in a single pass through the range of possible numbers after counting all occurrences.

Learn more about Math patterns.

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 employs a simple counting algorithm, straightforward data structures, and the pattern of frequency analysis. Here's a detailed walk-through aligned with the code from the Reference Solution Approach:

  1. Initialization of Data Structures: First, we initialize a counting array cnt, which is sized one element larger than n^2 (because our range is 1 to n^2 inclusive, and arrays are 0-indexed). We also set up an array ans of size 2 to store our final answer – the first element for the repeating number a and the second for the missing number b.

  2. Counting Occurrences:

    • We iterate over each row of the grid using a for loop.
    • Inside this loop, we iterate over each value v in the row.
    • We increment the count of v in our cnt array. This means for every occurrence of a number, its corresponding index in the cnt array is increased by 1. After this nested loop, cnt[v] will reflect the total number of times the number v has appeared in the grid.

  3. Identifying the Repeating and Missing Numbers:

    • We run a loop ranging from 1 to n^2.
    • For each i in this range, we perform the following checks:
      • If the count cnt[i] is 2, this means the number i is repeated. We assign this number i to the first element of ans, i.e., ans[0].
      • If the count cnt[i] is 0, this implies the number i was not found in the grid and hence is missing. We assign this number i to the second element of ans, i.e., ans[1].

The algorithm makes use of a simple counting technique which is very effective in situations where we need to track the frequency of elements and easily find discrepancies. By utilizing array indices that align with the value of the numbers in the grid, we eliminate the need for complex data structures or searching algorithms, providing a solution with O(n^2) time complexity (due to the two nested for loops) and O(n^2) space complexity (due to the cnt array).

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example Walkthrough

Let's assume we have a small 2x2 grid (so n=2), which contains the following numbers:

1[ [4, 2],
2  [2, 3] ]

In this grid, the number 2 appears twice (repeating number) and the number 1 is missing.

Step by step, we'll apply the solution approach to this grid:

1. Initialization of Data Structures

We initialize a counting array cnt of size 2^2 + 1 = 5 (because our range of numbers is 1 to 4, and we want an extra space for the 0-index which we won't use). The array cnt will look like this after initialization:

1cnt = [0, 0, 0, 0, 0]

We also initialize the answer array ans of size 2 which will eventually contain the repeating number at index 0 and the missing number at index 1:

1ans = [0, 0]

2. Counting Occurrences

We iterate over each row of the grid and for each number v we encounter, we increment cnt[v]:

  • In the first row, we encounter 4 and 2. After processing this row, cnt looks like:
1cnt = [0, 0, 1, 0, 1]
  • In the second row, we see 2 again (which will be incremented) and 3. The cnt array after processing the second row is:
1cnt = [0, 0, 2, 1, 1]

Now that we have finished counting, cnt[2] is 2, indicating number 2 has appeared twice, and cnt[1] is 0, showing that number 1 is missing.

3. Identifying the Repeating and Missing Numbers

We loop through the array cnt, starting from index 1 because our numbers also start from 1. For each index i, we check the value of cnt[i]:

  • cnt[1] = 0, which means 1 is missing, so we update ans[1] = 1.
  • cnt[2] = 2, which indicates that 2 is repeating, hence we set ans[0] = 2.

After this step, our answer array contains the repeating and missing numbers:

1ans = [2, 1]

This example illustrates the approach taken in solving the problem: by employing counting to track the frequency of elements and determining any discrepancies, we can find both the duplicating and missing numbers in the grid with relative efficiency and ease.

Solution Implementation

1class Solution:
2    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
3        # The size of the grid is n*n.
4        n = len(grid) 
5
6        # Create a count array initialized with zeros, of size n*n + 1.
7        # The extra 1 is to have an index equal to the maximum possible value in the grid.
8        count = [0] * (n * n + 1)
9
10        # Iterate over each row and each value in the grid, incrementing the corresponding count.
11        for row in grid:
12            for value in row:
13                count[value] += 1
14
15        # Initialize an answer list to store the repeated and missing values.
16        answer = [0, 0] 
17
18        # Go through the count array to find which value is repeated (count of 2)
19        # and which is missing (count of 0).
20        for i in range(1, n * n + 1):
21            if count[i] == 2:
22                answer[0] = i  # The repeated value.
23            elif count[i] == 0:
24                answer[1] = i  # The missing value.
25
26        # Return the answer list containing the repeated and missing values.
27        return answer
28
1class Solution {
2    // Method to find the missing and repeated values in a grid.
3    public int[] findMissingAndRepeatedValues(int[][] grid) {
4        // Calculate the size of the grid.
5        int n = grid.length;
6
7        // Initialize a count array to keep track of occurrences of each number.
8        int[] count = new int[n * n + 1]; // +1 because we are using 1-based indexing.
9      
10        // Array to store the final answer: [repeated number, missing number].
11        int[] answer = new int[2];
12      
13        // Iterate over the grid to count the occurrences of each number.
14        for (int[] row : grid) {
15            for (int num : row) {
16                // Increment the count of the current number.
17                count[num]++;
18              
19                // If a number appears twice, it is the repeated number.
20                if (count[num] == 2) {
21                    answer[0] = num;
22                }
23            }
24        }
25      
26        // Look for the missing number in the count array.
27        for (int i = 1; ; i++) {
28            // If a number has never appeared, it is the missing number.
29            if (count[i] == 0) {
30                answer[1] = i;
31                // Return the answer array with the repeated and missing numbers.
32                return answer;
33            }
34        }
35    }
36}
37
1#include <vector>
2
3class Solution {
4public:
5    // This function finds the missing and repeated values in a grid, where grid is
6    // a vector of vectors of integers, representing a NxN matrix.
7    // It returns a vector containing two integers, where the first integer is the
8    // repeated value and the second integer is the missing value from the grid.
9    std::vector<int> findMissingAndRepeatedValues(std::vector<std::vector<int>>& grid) {
10        int n = grid.size(); // Size of the grid (NxN matrix so size is N)
11        std::vector<int> count(n * n + 1, 0); // Count container to keep track of occurrences of numbers
12        std::vector<int> answer(2); // Vector to store the answer: [repeated_value, missing_value]
13      
14        // Iterate over the rows of the grid
15        for (auto& row : grid) {
16            // Iterate over the numbers in the current row
17            for (int number : row) {
18                // Increment the count for this number
19                count[number]++;
20                // If the count for this number becomes 2, then we found the repeated number
21                if (count[number] == 2) {
22                    answer[0] = number;
23                }
24            }
25        }
26      
27        // Find the missing number by looking for a count of 0
28        for (int number = 1; number <= n * n; ++number) {
29            if (count[number] == 0) {
30                answer[1] = number;
31                break;
32            }
33        }
34      
35        return answer; // Return the found repeated and missing values
36    }
37};
38
1function findMissingAndRepeatedValues(grid: number[][]): number[] {
2    // Determine the size of the grid (n by n).
3    const gridSize = grid.length;
4
5    // Initialize a counter array for numbers 1 to n^2, filled with 0s.
6    const count: number[] = Array(gridSize * gridSize + 1).fill(0);
7  
8    // Initialize the answer array with two elements for repeated and missing values.
9    const result: number[] = Array(2).fill(0);
10  
11    // Iterate over each row in the grid.
12    for (const row of grid) {
13        // Iterate over each element of the current row.
14        for (const value of row) {
15            // Increment the count for this value.
16            count[value]++;
17
18            // If the count reaches 2, we've found the repeated value.
19            if (count[value] === 2) {
20                result[0] = value; // Store the repeated value in the result array.
21            }
22        }
23    }
24  
25    // Look for the missing value.
26    for (let x = 1; x < count.length; x++) {
27        // The missing value will have a count of 0.
28        if (count[x] === 0) {
29            result[1] = x; // Store the missing value in the result array.
30            return result; // Return the result array with both repeated and missing values.
31        }
32    }
33
34    // Note: The loop is guaranteed to return within the size range of the grid,
35    // so no break condition or infinite loop risk is present here.
36}
37
Not Sure What to Study? Take the 2-min Quiz：

Depth first search can be used to find whether two components in a graph are connected.

Time and Space Complexity

The time complexity of the provided code is indeed O(n^2). This complexity arises due to the two nested loops, where the first for loop runs over all rows, and the inner loop over all values in each row, leading to a total of n * n operations, which represents the total number of elements in the grid.

The space complexity of the code is also O(n^2). This is because of the cnt list, which has n * n elements, with each spot representing the count of appearances for each possible value in the range from 1 to n * n.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

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

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 👨‍🏫