Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Find Missing and Repeated Values

HARDProblemSolveExternal Links

Description

You are given a 0-indexed 2D integer matrix grid of size n × n with values in the range [1, n²]. Every integer from 1 to n² appears exactly once in the grid, except for one number a which appears twice and another number b which is missing entirely.

Your task is to identify both the repeating number a and the missing number b, and return them as a 0-indexed integer array ans of size 2 where ans[0] equals a (the repeated value) and ans[1] equals b (the missing value).

In simpler terms, imagine you have a grid filled with numbers from 1 to n². Someone accidentally wrote one number twice and forgot to write another number at all. You need to find both: which number was written twice and which one was left out.

Examples

Example 1

Input: grid = [[1, 3], [2, 2]]

Output: [2, 4]

Explanation: The grid is 2×2, so numbers should range from 1 to 4. Flattening the grid gives us [1, 3, 2, 2]. The number 2 appears twice (it is the repeated value), and the number 4 is nowhere in the grid (it is the missing value). Therefore the answer is [2, 4].

Example 2

Input: grid = [[9, 1, 7], [8, 9, 2], [3, 4, 6]]

Output: [9, 5]

Explanation: The grid is 3×3, so numbers should range from 1 to 9. Flattening the grid gives [9, 1, 7, 8, 9, 2, 3, 4, 6]. The number 9 appears twice, and the number 5 is missing. Therefore the answer is [9, 5].

Example 3

Input: grid = [[1, 1]]

Output: [1, 2]

Explanation: The grid is 1×2 — wait, the grid must be n×n. For n=1, grid = [[1]] would have no missing or repeated. The smallest valid grid is n=2. In grid = [[1, 1], [3, 4]], flattening gives [1, 1, 3, 4]. Number 1 repeats and number 2 is missing. Answer: [1, 2].

Constraints

  • 2 ≤ n ≤ 50 (where n = grid.length = grid[i].length)
  • 1 ≤ grid[i][j] ≤ n × n
  • Exactly one value appears twice
  • Exactly one value from [1, n²] is missing
  • All other values appear exactly once

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to check each number from 1 to n² one by one and count how many times it appears in the grid.

Imagine you have a checklist of numbers from 1 to n². You go through the entire grid for each number on your checklist, counting how many times that number appears. If a number appears twice, it is the repeated value. If a number appears zero times, it is the missing value.

This approach requires no clever tricks — just brute-force counting — but it involves scanning the entire grid once for every possible number, making it slow for large inputs.

Step-by-Step Explanation

Let's trace through with grid = [[1, 3], [2, 2]] (n=2, so numbers range 1 to 4):

Step 1: Check number 1: scan entire grid → found at grid[0][0]. Count = 1. Neither repeated nor missing.

Step 2: Check number 2: scan entire grid → found at grid[1][0] and grid[1][1]. Count = 2. This is the repeated value! Set a = 2.

Step 3: Check number 3: scan entire grid → found at grid[0][1]. Count = 1. Neither repeated nor missing.

Step 4: Check number 4: scan entire grid → not found anywhere. Count = 0. This is the missing value! Set b = 4.

Step 5: Return [a, b] = [2, 4].

Brute Force — Counting Each Number in the Grid — Watch how we check every number from 1 to n² by scanning the entire flattened grid for each, counting occurrences to find the repeated and missing values.

Algorithm

  1. Let total = n × n (the total count of numbers expected)
  2. For each number num from 1 to total:
    a. Initialize count = 0
    b. Scan every cell in the grid; increment count whenever grid[i][j] equals num
    c. If count == 2, record num as the repeated value
    d. If count == 0, record num as the missing value
  3. Return [repeated, missing]

Code

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        int total = n * n;
        int repeated = -1, missing = -1;
        
        for (int num = 1; num <= total; num++) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == num) {
                        count++;
                    }
                }
            }
            if (count == 2) repeated = num;
            if (count == 0) missing = num;
        }
        
        return {repeated, missing};
    }
};
class Solution:
    def findMissingAndRepeatedValues(self, grid: list[list[int]]) -> list[int]:
        n = len(grid)
        total = n * n
        repeated = -1
        missing = -1
        
        for num in range(1, total + 1):
            count = 0
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == num:
                        count += 1
            if count == 2:
                repeated = num
            if count == 0:
                missing = num
        
        return [repeated, missing]
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int total = n * n;
        int repeated = -1, missing = -1;
        
        for (int num = 1; num <= total; num++) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == num) {
                        count++;
                    }
                }
            }
            if (count == 2) repeated = num;
            if (count == 0) missing = num;
        }
        
        return new int[]{repeated, missing};
    }
}

Complexity Analysis

Time Complexity: O(n⁴)

We check each of the n² possible numbers, and for each number we scan the entire n×n grid (n² cells). This gives us n² × n² = n⁴ operations. For n = 50, that is 50⁴ = 6,250,000 operations, which is manageable but wasteful.

Space Complexity: O(1)

We only use a few integer variables (count, repeated, missing). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach performs n⁴ operations because it repeatedly scans the entire grid for every single number. This is highly redundant — we visit every grid cell n² times in total.

The core inefficiency is that we are not remembering what we have already seen. Each time we look for a new number, we start from scratch and scan the entire grid again. If instead we processed the grid once and recorded the frequency of each number, we could immediately identify which number has frequency 2 (repeated) and which has frequency 0 (missing).

This insight leads us to a frequency counting approach using an auxiliary array, which reduces the time from O(n⁴) to O(n²).

Better Approach - Frequency Array

Intuition

Instead of scanning the grid repeatedly for each number, we can scan the grid just once and build a frequency table. Think of it like taking attendance in a classroom: instead of calling each student's name and looking around the room, you hand out a sign-in sheet and let everyone mark themselves. At the end, you check the sheet once — whoever signed twice is the repeater, and whoever did not sign at all is the missing person.

We create an array of size n² + 1 (to use 1-based indexing), initialized to zeros. As we traverse every cell in the grid, we increment the count at the index corresponding to that cell's value. After processing the entire grid, the index with count 2 is the repeated number, and the index with count 0 is the missing number.

Step-by-Step Explanation

Let's trace through with grid = [[1, 3], [2, 2]] (n=2, numbers 1 to 4):

Step 1: Create frequency array freq of size 5 (indices 0-4), all zeros: [0, 0, 0, 0, 0].

Step 2: Process grid[0][0] = 1. Increment freq[1]. freq = [0, 1, 0, 0, 0].

Step 3: Process grid[0][1] = 3. Increment freq[3]. freq = [0, 1, 0, 1, 0].

Step 4: Process grid[1][0] = 2. Increment freq[2]. freq = [0, 1, 1, 1, 0].

Step 5: Process grid[1][1] = 2. Increment freq[2]. freq = [0, 1, 2, 1, 0].

Step 6: Scan freq from index 1 to 4:

  • freq[1] = 1 → normal
  • freq[2] = 2 → REPEATED! Set a = 2.
  • freq[3] = 1 → normal
  • freq[4] = 0 → MISSING! Set b = 4.

Step 7: Return [2, 4].

Frequency Array — Single Pass Counting — Watch how we scan the grid once and build a frequency array. The number with frequency 2 is repeated, and the one with frequency 0 is missing.

Algorithm

  1. Let total = n × n
  2. Create a frequency array freq of size total + 1, initialized to 0
  3. Traverse every cell in the grid:
    • For each value grid[i][j], increment freq[grid[i][j]]
  4. Scan freq from index 1 to total:
    • If freq[i] == 2, record i as the repeated value
    • If freq[i] == 0, record i as the missing value
  5. Return [repeated, missing]

Code

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        int total = n * n;
        vector<int> freq(total + 1, 0);
        
        // Count frequency of each value
        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 <= total; i++) {
            if (freq[i] == 2) repeated = i;
            if (freq[i] == 0) missing = i;
        }
        
        return {repeated, missing};
    }
};
class Solution:
    def findMissingAndRepeatedValues(self, grid: list[list[int]]) -> list[int]:
        n = len(grid)
        total = n * n
        freq = [0] * (total + 1)
        
        # Count frequency of each value
        for row in grid:
            for val in row:
                freq[val] += 1
        
        repeated = -1
        missing = -1
        for i in range(1, total + 1):
            if freq[i] == 2:
                repeated = i
            if freq[i] == 0:
                missing = i
        
        return [repeated, missing]
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int total = n * n;
        int[] freq = new int[total + 1];
        
        // Count frequency of each value
        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 <= total; i++) {
            if (freq[i] == 2) repeated = i;
            if (freq[i] == 0) missing = i;
        }
        
        return new int[]{repeated, missing};
    }
}

Complexity Analysis

Time Complexity: O(n²)

We traverse the entire grid once (n² cells) to build the frequency array, then scan the frequency array once (n² entries). Total: O(n²) + O(n²) = O(n²). This is a massive improvement over the brute force O(n⁴).

Space Complexity: O(n²)

We use a frequency array of size n² + 1. For n = 50, this is 2501 integers — very manageable, but it is extra space proportional to the input size.

Why This Approach Is Not Efficient

The frequency array approach is already quite efficient at O(n²) time, which is optimal for reading the entire grid. However, it requires O(n²) extra space for the frequency array.

Can we find the repeated and missing numbers without any extra space beyond a few variables? Yes! The key insight is that mathematics gives us two equations we can set up using the expected sum and sum of squares of numbers from 1 to n². By comparing the expected values with the actual values computed from the grid, we can solve for the two unknowns (repeated and missing) using algebra alone — no auxiliary data structure needed.

This brings the space complexity down from O(n²) to O(1) while keeping time at O(n²).

Optimal Approach - Mathematical Equations

Intuition

Here is the brilliant mathematical insight: if we let a be the repeated number and b be the missing number, then the actual sum of all grid elements differs from the expected sum in a predictable way.

The expected sum of numbers 1 to N (where N = n²) is S_expected = N × (N+1) / 2. The actual sum S_actual includes a twice but excludes b, so:

S_actual = S_expected - b + a

Rearranging: a - b = S_actual - S_expected ... (Equation 1)

Similarly, the expected sum of squares is S2_expected = N × (N+1) × (2N+1) / 6. The actual sum of squares:

S2_actual = S2_expected - b² + a²

Rearranging: a² - b² = S2_actual - S2_expected ... (Equation 2)

Since a² - b² = (a - b)(a + b), we can divide Equation 2 by Equation 1 to get:

a + b = (S2_actual - S2_expected) / (S_actual - S_expected) ... (Equation 3)

Now we have two simple equations:

  • a - b = diff1 (from Equation 1)
  • a + b = diff2 (from Equation 3)

Solving: a = (diff1 + diff2) / 2, b = (diff2 - diff1) / 2

This is elegant because we only need to compute two sums while traversing the grid, requiring no extra data structures.

Step-by-Step Explanation

Let's trace through with grid = [[9, 1, 7], [8, 9, 2], [3, 4, 6]] (n=3, N=9):

Step 1: Compute expected sums.

  • S_expected = 9 × 10 / 2 = 45
  • S2_expected = 9 × 10 × 19 / 6 = 285

Step 2: Compute actual sums by traversing the grid.

  • Elements: 9, 1, 7, 8, 9, 2, 3, 4, 6
  • S_actual = 9 + 1 + 7 + 8 + 9 + 2 + 3 + 4 + 6 = 49
  • S2_actual = 81 + 1 + 49 + 64 + 81 + 4 + 9 + 16 + 36 = 341

Step 3: Compute differences.

  • diff1 = S_actual - S_expected = 49 - 45 = 4 (this equals a - b)
  • diff2_raw = S2_actual - S2_expected = 341 - 285 = 56 (this equals a² - b²)

Step 4: Compute a + b.

  • a + b = diff2_raw / diff1 = 56 / 4 = 14

Step 5: Solve the two equations.

  • a - b = 4
  • a + b = 14
  • Adding: 2a = 18, so a = 9 (repeated)
  • Subtracting: 2b = 10, so b = 5 (missing)

Step 6: Return [9, 5].

Mathematical Approach — Sum and Sum of Squares — Watch how we compute actual sums in a single pass, then use two mathematical equations to solve for the repeated and missing values without any extra data structures.

Algorithm

  1. Let N = n × n
  2. Compute expected sums:
    • S_expected = N × (N + 1) / 2
    • S2_expected = N × (N + 1) × (2N + 1) / 6
  3. Traverse every cell in the grid, accumulating:
    • S_actual (sum of all elements)
    • S2_actual (sum of squares of all elements)
  4. Compute:
    • diff1 = S_actual - S_expected (equals a - b)
    • diff2 = (S2_actual - S2_expected) / diff1 (equals a + b)
  5. Solve:
    • a (repeated) = (diff1 + diff2) / 2
    • b (missing) = (diff2 - diff1) / 2
  6. Return [a, b]

Code

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        long long N = (long long)n * n;
        
        long long S_expected = N * (N + 1) / 2;
        long long S2_expected = N * (N + 1) * (2 * N + 1) / 6;
        
        long long S_actual = 0, S2_actual = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long long val = grid[i][j];
                S_actual += val;
                S2_actual += val * val;
            }
        }
        
        // a - b = diff1
        long long diff1 = S_actual - S_expected;
        // a^2 - b^2 = diff2_raw => (a-b)(a+b) = diff2_raw
        long long diff2_raw = S2_actual - S2_expected;
        // a + b = diff2_raw / diff1
        long long sum_ab = diff2_raw / diff1;
        
        int repeated = (int)((diff1 + sum_ab) / 2);
        int missing = (int)((sum_ab - diff1) / 2);
        
        return {repeated, missing};
    }
};
class Solution:
    def findMissingAndRepeatedValues(self, grid: list[list[int]]) -> list[int]:
        n = len(grid)
        N = n * n
        
        S_expected = N * (N + 1) // 2
        S2_expected = N * (N + 1) * (2 * N + 1) // 6
        
        S_actual = 0
        S2_actual = 0
        for row in grid:
            for val in row:
                S_actual += val
                S2_actual += val * val
        
        # a - b = diff1
        diff1 = S_actual - S_expected
        # a^2 - b^2 = diff2_raw => (a-b)(a+b) = diff2_raw
        diff2_raw = S2_actual - S2_expected
        # a + b = diff2_raw / diff1
        sum_ab = diff2_raw // diff1
        
        repeated = (diff1 + sum_ab) // 2
        missing = (sum_ab - diff1) // 2
        
        return [repeated, missing]
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        long N = (long) n * n;
        
        long sExpected = N * (N + 1) / 2;
        long s2Expected = N * (N + 1) * (2 * N + 1) / 6;
        
        long sActual = 0, s2Actual = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long val = grid[i][j];
                sActual += val;
                s2Actual += val * val;
            }
        }
        
        // a - b = diff1
        long diff1 = sActual - sExpected;
        // a^2 - b^2 = diff2Raw => (a-b)(a+b) = diff2Raw
        long diff2Raw = s2Actual - s2Expected;
        // a + b = diff2Raw / diff1
        long sumAB = diff2Raw / diff1;
        
        int repeated = (int) ((diff1 + sumAB) / 2);
        int missing = (int) ((sumAB - diff1) / 2);
        
        return new int[]{repeated, missing};
    }
}

Complexity Analysis

Time Complexity: O(n²)

We traverse the entire grid exactly once (n² cells) to compute S_actual and S2_actual. The subsequent calculations (differences, solving equations) are all O(1) constant-time arithmetic operations. Total: O(n²).

Space Complexity: O(1)

We only use a fixed number of variables (S_expected, S2_expected, S_actual, S2_actual, diff1, diff2_raw, sum_ab, repeated, missing). No auxiliary data structures are created. This is the optimal space usage — we cannot do better than constant extra space while still reading the entire grid.