Description#
You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n2]. 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 <= n == grid.length == grid[i].length <= 501 <= grid[i][j] <= n * n- For all
x that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members. - For all
x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members. - For all
x that 1 <= x <= n * n except two of them there is exatly one pair of i, j that 0 <= i, j <= n - 1 and grid[i][j] == x.
Solutions#
Solution 1: Counting#
We create an array $cnt$ of length $n^2 + 1$ to count the frequency of each number in the matrix.
Next, we traverse $i \in [1, n^2]$. If $cnt[i] = 2$, then $i$ is the duplicated number, and we set the first element of the answer to $i$. If $cnt[i] = 0$, then $i$ is the missing number, and we set the second element of the answer to $i$.
The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the side length of the matrix.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
cnt = [0] * (n * n + 1)
for row in grid:
for v in row:
cnt[v] += 1
ans = [0] * 2
for i in range(1, n * n + 1):
if cnt[i] == 2:
ans[0] = i
if cnt[i] == 0:
ans[1] = i
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[] findMissingAndRepeatedValues(int[][] grid) {
int n = grid.length;
int[] cnt = new int[n * n + 1];
int[] ans = new int[2];
for (int[] row : grid) {
for (int x : row) {
if (++cnt[x] == 2) {
ans[0] = x;
}
}
}
for (int x = 1;; ++x) {
if (cnt[x] == 0) {
ans[1] = x;
return ans;
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> cnt(n * n + 1);
vector<int> ans(2);
for (auto& row : grid) {
for (int x : row) {
if (++cnt[x] == 2) {
ans[0] = x;
}
}
}
for (int x = 1;; ++x) {
if (cnt[x] == 0) {
ans[1] = x;
return ans;
}
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func findMissingAndRepeatedValues(grid [][]int) []int {
n := len(grid)
ans := make([]int, 2)
cnt := make([]int, n*n+1)
for _, row := range grid {
for _, x := range row {
cnt[x]++
if cnt[x] == 2 {
ans[0] = x
}
}
}
for x := 1; ; x++ {
if cnt[x] == 0 {
ans[1] = x
return ans
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| function findMissingAndRepeatedValues(grid: number[][]): number[] {
const n = grid.length;
const cnt: number[] = Array(n * n + 1).fill(0);
const ans: number[] = Array(2).fill(0);
for (const row of grid) {
for (const x of row) {
if (++cnt[x] === 2) {
ans[0] = x;
}
}
}
for (let x = 1; ; ++x) {
if (cnt[x] === 0) {
ans[1] = x;
return ans;
}
}
}
|
