Problem Informations

• Problem Index: 2965
• Problem Link: Find Missing and Repeated Values
• Topics: Array, Hash Table, Math, Matrix

Problem Description

You are given a 0-indexed 2D integer matrix grid of size $n \times n$ with values in the range $[1, n^2]$. Each integer appears exactly once except a which appears twice and b which is missing. The task is to find the repeating and missing numbers a and b.

Return a 0-indexed integer array ans of size $2$ where ans[0] equals to a and ans[1] equals to b.

Example 1:

Input: grid = [[1,3],[2,2]]
Output: [2,4]
Explanation: Number 2 is repeated and number 4 is missing so the answer is [2,4].

Example 2:

Input: grid = [[9,1,7],[8,9,2],[3,4,6]]
Output: [9,5]
Explanation: Number 9 is repeated and number 5 is missing so the answer is [9,5].

Constraints:

• $2 \leq n == \text{grid.length} == \text{grid}[i].\text{length} \leq 50$
• $1 \leq \text{grid}[i][j] \leq n \times n$
• For all $x$ that $1 \leq x \leq n \times n$ there is exactly one $x$ that is not equal to any of the grid members.
• For all $x$ that $1 \leq x \leq n \times n$ there is exactly one $x$ that is equal to exactly two of the grid members.
• For all $x$ that $1 \leq x \leq n \times n$ except two of them there is exactly one pair of $i, j$ that $0 \leq i, j \leq n - 1$ and $\text{grid}[i][j] == x$.

Intuition

The problem presents a scenario where we have a square matrix grid filled with integers ranging from 1 to $n^2$. Within this matrix, all integers appear exactly once, except for one integer which appears twice, and another integer which is missing entirely. The goal is to identify the integer that repeats (denoted as a) and the integer that is missing (b). Given the constraints, this problem can be efficiently solved by utilizing a counting mechanism to keep track of the encountered numbers while traversing the matrix. By doing so, not only can we detect the repeating number, but we can also establish which number is absent by omission.

Approach

The approach involves a straightforward traversal and checking mechanism:

1. Initialization:

   • Start by declaring an integer repeated_num to store the repeating number once it’s detected.
   • Determine the size of the grid len, which reflects both the dimensions of the matrix since it is square (i.e., $n \times n$).

2. Tracking Occurrences:

   • To keep track of which numbers have appeared, use a boolean vector used with a length of $n^2 + 1$, initialized to false. This vector acts like a hash map for numbers from 1 to $n^2$.

3. Traversing the Grid:

   • Iterate over each element in the grid. For each number num, check if it has been marked as true in used:
     • If num has already been encountered (i.e., used[num] is true), then this number is the repeated one. Assign it to repeated_num.
     • Otherwise, mark this num as true in the used array, indicating it has been seen.

4. Identifying the Missing Number:

   • After processing the entire grid, traverse the used vector starting from 1 to $n^2$. The index i where used[i] remains false identifies the missing number, as it was never encountered in the grid.

5. Return the Result:

   • Once both the repeated and the missing numbers are identified, return them as a vector in the order $[a, b]$.

This structured approach ensures that we efficiently find both the repeating and missing numbers in a single pass through the grid, followed by a simple scan for the missing number. The use of a boolean array is pivotal as it allows constant time checking and marking operations, crucial for adhering to performance constraints.

Code

C++

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        // 'repeated_num' will store the value that appears twice.
        int repeated_num;
        int len = grid.size(); // 'len' is the size of the grid, since it's square matrix.
        
        // 'used' is a vector to track numbers that have been encountered.
        vector<bool> used(len * len + 1, false);
        
        // Traverse each element in the 2D grid.
        for (vector<int>& row : grid) {
            for (int num : row) {
                // Check if the number has already appeared; if yes, assign it to 'repeated_num'.
                if (used[num]) {
                    repeated_num = num;
                }
                used[num] = true; // Mark the number as encountered.
            }
        }
        
        // Find the missing number by checking the 'used' vector.
        for (int i = 1; i < len * len + 1; i++) {
            if (!used[i]) {
                return {repeated_num, i};
            }
        }
        
        // Default return if logic fails, though per constraints should not occur.
        return {-1, -1};
    }
};

Python

class Solution:
    def findMissingAndRepeatedValues(self, grid):
        # 'repeated_num' will store the value that appears twice.
        repeated_num = None
        len_grid = len(grid)  # 'len' is the size of the grid, since it's square matrix.
        
        # 'used' is a list to track numbers that have been encountered.
        used = [False] * (len_grid * len_grid + 1)
        
        # Traverse each element in the 2D grid.
        for row in grid:
            for num in row:
                # Check if the number has already appeared; if yes, assign it to 'repeated_num'.
                if used[num]:
                    repeated_num = num
                used[num] = True  # Mark the number as encountered.
        
        # Find the missing number by checking the 'used' list.
        for i in range(1, len_grid * len_grid + 1):
            if not used[i]:
                return [repeated_num, i]
        
        # Default return if logic fails, though per constraints should not occur.
        return [-1, -1]

Complexity

• Time complexity: The time complexity is $O(n^2)$, where $n$ is the size of one dimension of the grid. This is because the algorithm iterates over each element in the $n \times n$ grid during the first nested loop to mark the used numbers. The second loop runs at most $n^2$ times to find the missing number, which is bounded by the same factor $n^2$. Thus, the overall time complexity is $O(n^2) + O(n^2) = O(n^2)$.

• Space complexity: The space complexity is $O(n^2)$. This arises from the ‘used’ vector, which is of size $n^2 + 1$ to accommodate all numbers ranging from $1$ to $n^2$. Other variables use constant space. Therefore, the dominant space requirement is for the ‘used’ vector, resulting in a space complexity of $O(n^2)$.