2965. Find Missing and Repeated Values

EasyArrayHash TableMathMatrix

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:

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.
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.
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.

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:

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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

[ [4, 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:

cnt = [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:

ans = [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:

cnt = [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:

cnt = [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:

ans = [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

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.

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

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know