Find Missing and Repeated Values

Easy
623.

Find Missing and Repeated Values

Find Missing and Repeated Values is an easy coding problem on hash table, math and matrix, asked in TCS, Infosys and Oracle interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var findMissingAndRepeatedValues = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Missing and Repeated Values — Problem & Solution

Find Missing and Repeated Values solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Missing and Repeated Values is an easy coding problem on hash table, math and matrix, asked in TCS, Infosys and Oracle interviews.

  • Difficulty: Easy
  • Topics: Hash Table, Math, Matrix
  • Asked at: TCS, Infosys, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Find Missing and Repeated Values

  1. Hint 1

    The values are bounded by n², which is exactly the number of cells — so a counting array is the natural structure.

  2. Hint 2

    Tally every cell, then scan the tallies: a 2 is the repeat, a 0 is the missing value.

  3. Hint 3

    The O(1)-space alternative compares the actual sum and sum of squares with their expected values.

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]

Java

public static int[] findMissingAndRepeatedValues(int[][] grid) {
    int n = grid.length;
    int total = n * n;
    int[] count = new int[total + 1];
    for (int[] row : grid) {
        for (int v : row) count[v]++;
    }
    int rep = 0, miss = 0;
    for (int v = 1; v <= total; v++) {
        if (count[v] == 2) rep = v;
        else if (count[v] == 0) miss = v;
    }
    return new int[] { rep, miss };
}

C++

vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    int total = n * n;
    vector<int> count(total + 1, 0);
    for (auto& row : grid) {
        for (int v : row) count[v]++;
    }
    int rep = 0, miss = 0;
    for (int v = 1; v <= total; v++) {
        if (count[v] == 2) rep = v;
        else if (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Matrix and Grid Traversal