Find Missing and Repeated Values — Easy Problem & Solution

Problem statement

You are given an n x n grid that should contain each integer from 1 to n² exactly once. Instead one value a appears twice and one value b is missing.

Return [a, b].

Example 1

Input: grid = [[1,3],[2,2]]
Output: [2,4]
Explanation: 2 appears twice and 4 never appears.

Example 2

Input: grid = [[9,1,7],[8,9,2],[3,4,6]]
Output: [9,5]
Explanation: 9 is repeated and 5 is missing.

Example 3

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

Constraints

• 2 <= n <= 50
• grid.length == grid[i].length == n
• 1 <= grid[i][j] <= n * n
• Exactly one value repeats and exactly one is missing.

How to solve Find Missing and Repeated Values

Flatten the grid into a tally over 1 .. n². Exactly one value lands on 2 and exactly one on 0, which is precisely the pair being asked for.

Approach

1. Allocate count of size n² + 1, all zeros.
2. Increment count[v] for every cell value v.
3. Scan v from 1 to n²: record v as the repeat when count[v] == 2 and as the missing value when count[v] == 0.
4. Return [repeat, missing].

Why it works

There are n² cells and n² candidate values; one duplicate forces exactly one omission, so the tallies are all 1 except a single 2 and a single 0.

Complexity

• Time — O(n²)
• Space — O(n²)

Pitfalls

• Returning [missing, repeat] — the order is repeat first.
• Sizing the counting array at n rather than n² overflows on the first large cell.

Reference solution

Python

from typing import List

def findMissingAndRepeatedValues(grid: List[List[int]]) -> List[int]:
    n = len(grid)
    total = n * n
    count = [0] * (total + 1)
    for row in grid:
        for v in row:
            count[v] += 1
    rep = miss = 0
    for v in range(1, total + 1):
        if count[v] == 2:
            rep = v
        elif count[v] == 0:
            miss = v
    return [rep, miss]

JavaScript

var findMissingAndRepeatedValues = function(grid) {
    var n = grid.length;
    var total = n * n;
    var count = [];
    for (var t = 0; t <= total; t++) count.push(0);
    for (var r = 0; r < n; r++) {
        for (var c = 0; c < n; c++) count[grid[r][c]]++;
    }
    var rep = 0, miss = 0;
    for (var v = 1; v <= total; v++) {
        if (count[v] === 2) rep = v;
        else if (count[v] === 0) miss = v;
    }
    return [rep, miss];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Delete Greatest Value in Each Row Easy
• Modify the Matrix Easy
• Find Champion I Easy
• Prime In Diagonal Easy
• Matrix Similarity After Cyclic Shifts Easy
• Special Positions in a Binary Matrix Easy