Skip to content

2965. Find Missing and Repeated Values 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 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:
  vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
    const int n = grid.size();
    const int nSquared = n * n;
    vector<int> count(nSquared + 1);

    for (const vector<int>& row : grid)
      for (const int num : row)
        ++count[num];

    int repeated = -1;
    int missing = -1;

    for (int i = 1; i <= nSquared; ++i) {
      if (count[i] == 2)
        repeated = i;
      if (count[i] == 0)
        missing = i;
    }

    return {repeated, missing};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int[] findMissingAndRepeatedValues(int[][] grid) {
    final int n = grid.length;
    final int nSquared = n * n;
    int[] count = new int[nSquared + 1];

    for (int[] row : grid)
      for (final int num : row)
        ++count[num];

    int repeated = -1;
    int missing = -1;

    for (int i = 1; i <= nSquared; ++i) {
      if (count[i] == 2)
        repeated = i;
      if (count[i] == 0)
        missing = i;
    }

    return new int[] {repeated, missing};
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def findMissingAndRepeatedValues(self, grid: list[list[int]]) -> list[int]:
    count = [1] + [0] * len(grid)**2  # padding for 1-indexed

    for row in grid:
      for num in row:
        count[num] += 1

    return [count.index(2), count.index(0)]