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 <= 50grid.length == grid[i].length == n1 <= grid[i][j] <= n * nExactly one value repeats and exactly one is missing.
Hints for Find Missing and Repeated Values
Hint 1
The values are bounded by
n², which is exactly the number of cells — so a counting array is the natural structure.Hint 2
Tally every cell, then scan the tallies: a
2is the repeat, a0is the missing value.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
- Allocate
countof sizen² + 1, all zeros. - Increment
count[v]for every cell valuev. - Scan
vfrom1ton²: recordvas the repeat whencount[v] == 2and as the missing value whencount[v] == 0. - 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
nrather thann²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