Find Missing and Repeated Values

easy math matrix hash table

Problem

You are given an n × n grid whose values come from the range [1, n²]. Every number appears exactly once except one value a that appears twice and one value b that is missing. Return [a, b] — the repeated number and the missing number.

Inputgrid = [[1,3],[2,2]]

Output[2, 4]

Here n = 2, so values run 1..4. Number 2 appears twice and number 4 never appears, so the answer is [2, 4].

grid (rows separated by ;, values by ,)

def findMissingAndRepeatedValues(grid):
    n = len(grid)
    count = [0] * (n * n + 1)        # count[v] = how often v appears
    for row in grid:                 # tally every cell of the grid
        for v in row:
            count[v] += 1
    a = b = -1
    for v in range(1, n * n + 1):    # scan all candidate values
        if count[v] == 2:
            a = v                    # appears twice -> repeated
        elif count[v] == 0:
            b = v                    # never appears -> missing
    return [a, b]

function findMissingAndRepeatedValues(grid) {
  const n = grid.length;
  const count = new Array(n * n + 1).fill(0); // count[v] = frequency
  for (const row of grid)                     // tally every cell
    for (const v of row) count[v]++;
  let a = -1, b = -1;
  for (let v = 1; v <= n * n; v++) {          // scan candidates
    if (count[v] === 2) a = v;                // repeated value
    else if (count[v] === 0) b = v;           // missing value
  }
  return [a, b];
}

int[] findMissingAndRepeatedValues(int[][] grid) {
    int n = grid.length;
    int[] count = new int[n * n + 1];   // count[v] = frequency
    for (int[] row : grid)              // tally every cell
        for (int v : row) count[v]++;
    int a = -1, b = -1;
    for (int v = 1; v <= n * n; v++) {  // scan candidates
        if (count[v] == 2) a = v;       // repeated value
        else if (count[v] == 0) b = v;  // missing value
    }
    return new int[]{a, b};
}

vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<int> count(n * n + 1, 0);   // count[v] = frequency
    for (auto& row : grid)            // tally every cell
        for (int v : row) count[v]++;
    int a = -1, b = -1;
    for (int v = 1; v <= n * n; v++) { // scan candidates
        if (count[v] == 2) a = v;      // repeated value
        else if (count[v] == 0) b = v; // missing value
    }
    return {a, b};
}

Explanation

Because the grid is n × n and its entries are drawn from 1 … n², there are exactly as many cells as there are legal values. If nothing were wrong, every value would show up once. The twist is that one value a sneaks in twice and another value b never appears at all.

The cleanest way to expose both anomalies is a frequency count. We allocate an array count indexed by value (size n² + 1 so we can index by the value itself), then walk every cell of the grid and do count[v] += 1.

After the tally, each legitimate value has a count of 1. The single value whose count is 2 is the repeated number a; the single value whose count is 0 is the missing number b. One pass over 1 … n² finds both.

Example: grid = [[1,3],[2,2]]. Tallying gives counts 1→1, 2→2, 3→1, 4→0. Value 2 has count 2 (repeated) and value 4 has count 0 (missing), so the answer is [2, 4].

There is also an elegant O(1) space algebraic trick using the sum and sum-of-squares of 1 … n², but the counting method is the most transparent and is what the visualizer above traces step by step.

Time: O(n²) Space: O(n²)