# Find Missing and Repeated Values
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-missing-and-repeated-values)
Canonical: https://scaleengineer.com/dsa/problems/find-missing-and-repeated-values
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Hash Table, Matrix
---
## 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`_._

**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 <= 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 exactly one pair of `i, j` that `0 <= i, j <= n - 1` and `grid[i][j] == x`.

# Approaches
## Brute Force Iteration
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible number that could be in the grid (from 1 to n²) and, for each of these numbers, iterating through the entire grid to count how many times it appears. This allows us to identify which number appears twice and which number appears zero times.
**Time:** O(n⁴), where n is the dimension of the grid. The outer loop runs n² times, and for each iteration, we traverse the n x n grid, which takes n² operations. This results in a total complexity of O(n² * n²) = O(n⁴). · **Space:** O(1), as we only use a few variables to store the counts and results, regardless of the input size.
**Pros:** Simple to understand and implement.; Requires no extra space (O(1) space complexity).
**Cons:** Extremely inefficient due to the nested loops.; Not a practical solution for the given constraints, and would likely time out in a coding platform environment.
### Explanation
This method systematically checks every candidate number against every element in the grid. We loop from `k = 1` to `n*n`. In each iteration of this outer loop, we perform a full scan of the `n x n` grid. During the scan, we count how many times the number `k` is present. According to the problem statement, one number will have a count of 2 (the repeated one), one will have a count of 0 (the missing one), and all others will have a count of 1. We store these numbers when we find them and return the result.

```java
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int repeated = -1, missing = -1;
        for (int k = 1; k <= n * n; k++) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == k) {
                        count++;
                    }
                }
            }
            if (count == 2) {
                repeated = k;
            }
            if (count == 0) {
                missing = k;
            }
        }
        return new int[]{repeated, missing};
    }
}
```
### Algorithm
- Initialize two variables, `repeated` and `missing`, to store the results.
- Iterate through each number `k` from 1 to `n*n`.
- For each `k`, initialize a `count` to 0.
- Traverse the entire `grid` to count the occurrences of `k`.
- After counting, check the value of `count`:
  - If `count` is 2, then `k` is the repeated number. Store it in `repeated`.
  - If `count` is 0, then `k` is the missing number. Store it in `missing`.
- Once both `repeated` and `missing` are found, you can break the loops.
- Return the `[repeated, missing]` array.

## Sorting the Elements
This approach improves upon the brute-force method by first transforming the 2D grid into a 1D array and then sorting it. Once the array is sorted, finding the repeated element becomes trivial. The missing element can then be deduced using the sum of the elements.
**Time:** O(n² log n), as sorting an array of size n² takes O(n² log(n²)) which simplifies to O(n² log n). · **Space:** O(n²), for storing the flattened copy of the grid.
**Pros:** Significantly more efficient than the brute-force approach.; The logic is relatively straightforward to follow.
**Cons:** Requires O(n²) extra space to store the flattened array.; The time complexity is dominated by sorting, making it less efficient than linear time solutions.
### Explanation
First, we flatten the `n x n` grid into a 1D array of size `n²`. This makes it easier to apply standard array algorithms. Then, we sort this array. After sorting, any repeated elements will be adjacent to each other, so a single pass through the sorted array can find the repeated number `a`. To find the missing number `b`, we can use a mathematical trick. We know the sum of all numbers in the grid (`actualSum`) and the expected sum if no numbers were missing or repeated (`expectedSum`). The difference between these sums is related to `a` and `b` by the equation `actualSum - expectedSum = a - b`. Since we've already found `a`, we can easily solve for `b`.

```java
import java.util.Arrays;

class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int[] flatArr = new int[n * n];
        long actualSum = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                flatArr[k++] = grid[i][j];
                actualSum += grid[i][j];
            }
        }

        Arrays.sort(flatArr);

        int repeated = -1;
        for (int i = 1; i < n * n; i++) {
            if (flatArr[i] == flatArr[i - 1]) {
                repeated = flatArr[i];
                break;
            }
        }

        long N = n * n;
        long expectedSum = N * (N + 1) / 2;
        int missing = (int) (expectedSum - actualSum + repeated);

        return new int[]{repeated, missing};
    }
}
```
### Algorithm
- Create a new 1D array, `flatArr`, of size `n*n`.
- Iterate through the `grid` and copy all its elements into `flatArr`. While doing so, calculate the sum of all elements in the grid, `actualSum`.
- Sort the `flatArr`. The time complexity of this step will dominate.
- Iterate through the sorted `flatArr` from the second element. If `flatArr[i]` is equal to `flatArr[i-1]`, this is the repeated number `a`.
- Calculate the expected sum of numbers from 1 to `n*n`: `expectedSum = (n*n * (n*n + 1)) / 2`.
- The missing number `b` can be found using the formula: `b = expectedSum - actualSum + a`.
- Return `[a, b]`.

## Using a Frequency Counter
A more efficient approach is to use a frequency counter. Since the numbers are within a known range `[1, n²]`, we can use an array as a direct-address table (or a hash map) to count the occurrences of each number. This allows us to find the repeated and missing numbers in linear time relative to the number of elements in the grid.
**Time:** O(n²), as we make two separate passes, one over the grid (n² elements) and one over the frequency array (n² elements). · **Space:** O(n²), to store the frequency counts for numbers from 1 to n².
**Pros:** Efficient time complexity of O(n²).; Simple to implement and understand.
**Cons:** Requires O(n²) extra space, which can be substantial for large n.
### Explanation
This method involves two main passes. In the first pass, we iterate through all `n*n` elements of the grid. For each element, we use its value as an index into a frequency array and increment the count at that index. This effectively counts how many times each number from 1 to `n*n` appears in the grid. In the second pass, we iterate through the frequency array from index 1 to `n*n`. The index where the count is 2 corresponds to the repeated number, and the index where the count is 0 corresponds to the missing number.

```java
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int[] freq = new int[n * n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                freq[grid[i][j]]++;
            }
        }

        int repeated = -1, missing = -1;
        for (int i = 1; i <= n * n; i++) {
            if (freq[i] == 2) {
                repeated = i;
            }
            if (freq[i] == 0) {
                missing = i;
            }
        }
        return new int[]{repeated, missing};
    }
}
```
### Algorithm
- Create an integer array `freq` of size `n*n + 1`, initialized to all zeros. This array will act as a frequency map.
- Iterate through each element `val` in the input `grid`.
- For each `val`, increment its corresponding count in the frequency array: `freq[val]++`.
- After populating the `freq` array, initialize `repeated = -1` and `missing = -1`.
- Iterate from `i = 1` to `n*n`.
- Check the count for each number `i` in `freq[i]`:
  - If `freq[i] == 2`, then `i` is the repeated number.
  - If `freq[i] == 0`, then `i` is the missing number.
- Return `[repeated, missing]`.

## Mathematical Approach using Sums
The most optimal solution in terms of both time and space complexity involves using mathematical properties. By calculating the difference between the expected sum (and sum of squares) of numbers from 1 to n² and the actual sum (and sum of squares) of the numbers in the grid, we can form a system of two equations with two variables (the repeated number `a` and the missing number `b`) and solve for them.
**Time:** O(n²), as it requires only a single pass over the grid to compute the sums. · **Space:** O(1), as it only requires a few variables to store the sums, independent of the input size.
**Pros:** Optimal time complexity of O(n²).; Optimal space complexity of O(1).; Does not modify the input grid.
**Cons:** The sums can become very large, requiring the use of 64-bit integers (`long`) to avoid overflow.; The mathematical logic is less intuitive than other approaches.
### Explanation
This elegant approach avoids any extra space. Let `N = n²`. The set of numbers should be `{1, 2, ..., N}`. Let the repeated number be `a` and the missing number be `b`. We can establish two key relationships:
1.  **Sum Difference:** The sum of the grid's elements will be `Sum(1..N) - b + a`. Therefore, `(actual sum) - (expected sum) = a - b`.
2.  **Sum of Squares Difference:** The sum of the squares of the grid's elements will be `Sum(1²..N²) - b² + a²`. Therefore, `(actual sum of squares) - (expected sum of squares) = a² - b²`.

We can calculate the actual sums by iterating through the grid once. The expected sums can be calculated using well-known formulas. This gives us the values for `a - b` and `a² - b²`. Since `a² - b² = (a - b)(a + b)`, we can find `a + b`. With `a - b` and `a + b` known, we can easily find `a` and `b`.

```java
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        long N = (long)n * n;
        
        long expectedSum = N * (N + 1) / 2;
        long expectedSumSq = N * (N + 1) * (2 * N + 1) / 6;
        
        long actualSum = 0;
        long actualSumSq = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long val = grid[i][j];
                actualSum += val;
                actualSumSq += val * val;
            }
        }
        
        // a - b = actualSum - expectedSum
        long diffSum = actualSum - expectedSum;
        
        // a^2 - b^2 = actualSumSq - expectedSumSq
        long diffSumSq = actualSumSq - expectedSumSq;
        
        // a + b = (a^2 - b^2) / (a - b)
        long sumAB = diffSumSq / diffSum;
        
        // 2a = (a - b) + (a + b)
        int repeated = (int) ((diffSum + sumAB) / 2);
        
        // 2b = (a + b) - (a - b)
        int missing = (int) ((sumAB - diffSum) / 2);
        
        return new int[]{repeated, missing};
    }
}
```
### Algorithm
- Let `N = n*n`.
- Calculate the sum and sum of squares for a perfect sequence from 1 to N.
  - `expectedSum = N * (N + 1) / 2`
  - `expectedSumSq = N * (N + 1) * (2*N + 1) / 6`
- Initialize `actualSum = 0` and `actualSumSq = 0`. Use `long` data type to prevent overflow.
- Iterate through the `grid` and calculate the actual sum and sum of squares of its elements.
- Let `a` be the repeated number and `b` be the missing number.
- We can derive two equations:
  - `a - b = actualSum - expectedSum`
  - `a² - b² = actualSumSq - expectedSumSq`
- From the second equation, we know `(a - b)(a + b) = a² - b²`. We can find `a + b` by dividing `(a² - b²)` by `(a - b)`.
- Now we have a system of two linear equations for `a` and `b`:
  - `a - b = C1`
  - `a + b = C2`
- Solve for `a` and `b`:
  - `a = (C1 + C2) / 2`
  - `b = (C2 - C1) / 2`
- Return `[a, b]`.

# Solutions
### Java

```java
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;
      }
    }
  }
}

```

### Python

```python
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

```

### CPP

```cpp
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;
      }
    }
  }
};

```