Find Missing and Repeated Values

How it works

We can solve this without extra data structures using mathematical formulas. Let a be the repeated number and b be the missing number. The sum of the grid differs from the expected sum (1 + 2 + ... + n*n) by exactly a - b. Similarly, the sum of squares differs by a^2 - b^2. From these two equations, we can derive a + b (since a^2 - b^2 = (a - b)(a + b)), and then solve for both values.

Steps

1. Compute the sum and sum of squares of all elements in the grid.
2. Calculate the expected sum using the formula: n*n * (n*n + 1) / 2.
3. Calculate the expected sum of squares using: n*n * (n*n + 1) * (2*n*n + 1) / 6.
4. Let diff = gridSum - expectedSum, which equals a - b.
5. Let sqDiff = gridSqSum - expectedSqSum, which equals a^2 - b^2.
6. Compute sum = sqDiff / diff, which equals a + b.
7. Solve: a = (sum + diff) / 2 and b = sum - a.
8. Return [a, b].

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(1)

Things to watch for

Confusing Grid Size with Value Range

The grid has dimensions n x n, but values range from 1 to n*n. Using n instead of n*n as the upper bound when checking for missing or repeated values causes you to miss numbers greater than n. Always iterate through 1 to n*n when scanning for the missing and repeated values.

Integer Overflow in Math Approach

When using the mathematical solution with sum of squares, the values can grow very large. For an n x n grid, the sum of squares formula involves n^4 terms, which can overflow 32-bit integers. Use 64-bit integers (long in Java, long long in C++) for intermediate calculations to avoid incorrect results from overflow.

from typing import List

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        N = len(grid)
        gridSum = 0
        gridSqSum = 0

        for i in range(N):
            for j in range(N):
                gridSum += grid[i][j]
                gridSqSum += grid[i][j] * grid[i][j]

        totSum = (N * N * (N * N + 1)) // 2
        diff = gridSum - totSum  # a - b

        totSqSum = (N * N * (N * N + 1) * (2 * N * N + 1)) // 6
        sqDiff = gridSqSum - totSqSum  # (a^2) - (b^2)

        sum = sqDiff // diff  # a + b

        a = (sum + diff) // 2
        b = sum - a
        return [a, b]

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int N = grid.size();
        long long gridSum = 0;
        long long gridSqSum = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                gridSum += grid[i][j];
                gridSqSum += 1LL * grid[i][j] * grid[i][j];
            }
        }

        long long totSum = 1LL * N * N * (N * N + 1) / 2;
        long long diff = gridSum - totSum; // a - b

        long long totSqSum = 1LL * N * N * (N * N + 1) * (2 * N * N + 1) / 6;
        long long sqDiff = gridSqSum - totSqSum; // (a^2) - (b^2)

        long long sum = sqDiff / diff; // a + b

        int a = (sum + diff) / 2;
        int b = sum - a;

        return {a, b};
    }
};