Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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 <= 50
  • 1 <= 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.

Solution

Method 1 - Using frequency map

To solve this problem, we need to identify the number that appears twice (a) and the number that is missing (b) in the given n x n matrix.

Here is how we can do that:

  1. Flatten the Matrix: We need to work with all numbers in the matrix in a single dimension. Flatten the n x n grid into a 1D array of size n^2.
  2. Frequency Count:
    • Use a frequency array or map to count occurrences of numbers from 1 to n^2.
    • The number with a frequency of 2 is the repeating number a.
    • The number with a frequency of 0 is the missing number b.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int total = n * n;
        
        int[] freq = new int[total + 1];
        int a = -1, b = -1;
        
        // Count frequencies of all numbers in the grid
        for (int[] row : grid) {
            for (int num : row) {
                freq[num]++;
            }
        }
        
        // Find the repeating `a` and missing `b`
        for (int i = 1; i <= total; i++) {
            if (freq[i] == 2) a = i;  // Repeating number
            if (freq[i] == 0) b = i;  // Missing number
        }
        
        return new int[] {a, b};
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n: int = len(grid)
        total: int = n * n
        
        freq: List[int] = [0] * (total + 1)
        a: int = -1
        b: int = -1
        
        # Count frequencies of all numbers in the grid
        for row in grid:
            for num in row:
                freq[num] += 1
        
        # Find the repeating `a` and missing `b`
        for i in range(1, total + 1):
            if freq[i] == 2:
                a = i  # Repeating number
            if freq[i] == 0:
                b = i  # Missing number
        
        return [a, b]

Complexity

  • ⏰ Time complexity: O(n^2) because we process each element of the grid.
  • 🧺 Space complexity: O(n^2) for storing the frequency count.