Find Missing and Repeated Values solution and explanation
Google
9 more videos on this problem
Find Missing and Repeated Values - Leetcode 2965 - PythonNeetCodeIO · 7:34 · 9K views
Find Missing and Repeated Values | Mathematical Proof | Leetcode 2965 | codestorywithMIKcodestorywithMIK · 25:51 · 7K views
2965. Find Missing and Repeated Values | leetcode daily challenge | faang | shashcodeShashCode · 10:46 · 7K views
Find Missing and Repeated Values | Leetcode 2965Techdose · 9:50 · 4K views
Leetcode | 2965. Find Missing and Repeated Values | Easy | Java SolutionDeveloper Docs · 5:36 · 2K views
Find Missing and Repeated Values | LeetCode 2965 Java Solution Step-by-Step Explanation | FAANG DSARAHUL VIJAYAN · 15:17 · 734 views
2965. Find Missing and Repeated Values | Java | Leetcode |JavAttack · 9:47 · 196 views
Find Missing and Repeated Values - Leetcode 2965 - PythonTim Huang · 3:28 · 116 views
LeetCode 2965 Find Missing and Repeated Values | Math | Asked in GoogleCode Harmony · 23:13 · 115 views
2965. Find Missing and Repeated Values | Hash Map | Frequency Map | O(N) | LeetCodeLeet's Code · 9:05 · 72 views
The problem
You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n2]. Each integer appears exactly once except a which appears twice and b which is missing. The task is to find the repeating and missing numbers a and b.
Return a 0-indexed integer array ans of size 2 where ans[0] equals to a and ans[1] equals to b.
Example 1:
Input: grid = [[1,3],[2,2]] Output: [2,4] Explanation: Number 2 is repeated and number 4 is missing so the answer is [2,4].
Example 2:
Input: grid = [[9,1,7],[8,9,2],[3,4,6]] Output: [9,5] Explanation: Number 9 is repeated and number 5 is missing so the answer is [9,5].
Constraints:
2 <= n == grid.length == grid[i].length <= 501 <= grid[i][j] <= n * n- For all
xthat1 <= x <= n * nthere is exactly onexthat is not equal to any of the grid members. - For all
xthat1 <= x <= n * nthere is exactly onexthat is equal to exactly two of the grid members. - For all
xthat1 <= x <= n * nexcept two of them there is exatly one pair ofi, jthat0 <= i, j <= n - 1andgrid[i][j] == x.
Approach overview
Problem Overview: You receive an n x n matrix containing numbers from 1 to n². Exactly one number appears twice and one number is missing. Your job is to identify the repeated value and the missing value.
Approach 1: Counting Frequency Approach (O(n²) time, O(n²) space)
Traverse the grid and count how often each value appears. Since valid values range from 1 to n², allocate a frequency array of size n² + 1. Iterate through the matrix and increment the counter for each number. After the pass, scan the frequency array: the value with count 2 is the repeated number and the value with count 0 is the missing one. The algorithm performs straightforward iteration and constant‑time index lookups, which makes it easy to implement and very reliable. This approach works well whenever extra memory proportional to n² is acceptable and the input structure is a matrix or array.
Approach 2: Mathematical Summation Approach (O(n²) time, O(1) space)
The numbers should normally sum to S = n²(n² + 1) / 2, and the sum of squares should be Sq = n²(n² + 1)(2n² + 1) / 6. While iterating through the grid once, compute the actual sum and sum of squares. Let the repeated number be r and the missing number be m. The difference between expected and actual sums gives m - r, while the difference between square sums gives m² - r². Using the identity m² - r² = (m - r)(m + r), you can derive m + r and solve the two equations to obtain both numbers. This technique avoids extra storage and relies purely on arithmetic, which makes it ideal for memory‑constrained environments and common in math-based interview questions.
Recommended for interviews: Start with the counting approach because it clearly demonstrates understanding of frequency tracking using a hash table or array index. Then mention the mathematical solution as an optimization that reduces space complexity to O(1). Interviewers typically appreciate candidates who recognize the simple counting method first and then derive the formula-based improvement.
Approach 1: Counting Frequency Approach
This approach involves using an auxiliary data structure (like a hash table or array) to keep track of the frequency of each number from 1 to n*n. As we iterate over each cell in the grid, we increment the count of each number's occurrence:
- If a number appears twice, it becomes the duplicate number 'a'.
- If a number does not appear at all, it becomes the missing number 'b'.
def findMissingAndRepeated(grid):
n = len(grid)
count = [0] * (n * n + 1)
repeated = -1
missing = -1
for row in grid:
for num in row:
count[num] += 1
for num in range(1, n * n + 1):
if count[num] == 2:
repeated = num
elif count[num] == 0:
missing = num
return [repeated, missing]import java.util.Arrays;
public class Solution {
public int[] findMissingAndRepeated(int[][] grid) {
int n = grid.length;
int[] count = new int[n * n + 1];
int repeated = -1, missing = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count[grid[i][j]]++;
}
}
for (int num = 1; num <= n * n; num++) {
if (count[num] == 2) repeated = num;
if (count[num] == 0) missing = num;
}
return new int[]{repeated, missing};
}
}#include <vector>
using namespace std;
vector<int> findMissingAndRepeated(vector<vector<int>>& grid) {
int n = grid.size();
vector<int> count(n * n + 1, 0);
int repeated = -1, missing = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count[grid[i][j]]++;
}
}
for (int num = 1; num <= n * n; num++) {
if (count[num] == 2) repeated = num;
if (count[num] == 0) missing = num;
}
return {repeated, missing};
}function findMissingAndRepeated(grid) {
const n = grid.length;
const count = Array(n * n + 1).fill(0);
let repeated = -1;
let missing = -1;
for (const row of grid) {
for (const num of row) {
count[num]++;
}
}
for (let num = 1; num <= n * n; num++) {
if (count[num] === 2) {
repeated = num;
} else if (count[num] === 0) {
missing = num;
}
}
return [repeated, missing];
}#include <stdio.h>
#include <stdlib.h>
int* findMissingAndRepeated(int** grid, int n, int* returnSize) {
int* count = (int*)calloc(n * n + 1, sizeof(int));
int repeated = -1, missing = -1;
*returnSize = 2;
int *ans = (int*)malloc(2 * sizeof(int));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count[grid[i][j]]++;
}
}
for (int num = 1; num <= n * n; num++) {
if (count[num] == 2) repeated = num;
if (count[num] == 0) missing = num;
}
free(count);
ans[0] = repeated;
ans[1] = missing;
return ans;
}using System;
public class Solution {
public int[] FindMissingAndRepeated(int[][] grid) {
int n = grid.Length;
int[] count = new int[n * n + 1];
int repeated = -1, missing = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count[grid[i][j]]++;
}
}
for (int num = 1; num <= n * n; num++) {
if (count[num] == 2) repeated = num;
if (count[num] == 0) missing = num;
}
return new int[]{repeated, missing};
}
}Utilizing a list in Python, we track each number's frequency. The frequencies lead us to identify which numbers are missing or repeated.
Time complexity: O(n^2), Space complexity: O(n^2)
Approach 2: Mathematical Summation Approach
This approach relies on mathematical properties, specifically the sum of the first n natural numbers and the sum of their squares. By computing the expected sums and comparing them to the actual sums of the grid, the repeated and missing values can be deduced.
The difference between the expected sum and the actual sum yields an equation involving the missing and duplicate numbers which can be solved to find both missing and duplicate numbers.
def findMissingAndRepeated(grid):
n = len(grid)
sum_actual = 0
sumSq_actual = 0
expectedSum = n * n * (n * n + 1) // 2
expectedSumSq = n * n * (n * n + 1) * (2 * n * n + 1) // 6
for row in grid:
for num in row:
sum_actual += num
sumSq_actual += num ** 2
diff = expectedSum - sum_actual
diffSq = expectedSumSq - sumSq_actual
b_plus_a = diffSq // diff
b = (diff + b_plus_a) // 2
a = b + diff
return [a, b]public class Solution {
public int[] findMissingAndRepeated(int[][] grid) {
int n = grid.length;
long sum = 0, sumSq = 0;
long expectedSum = ((long)n * n * (n * n + 1)) / 2;
long expectedSumSq = ((long)n * n * (n * n + 1) * (2 * n * n + 1)) / 6;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum += grid[i][j];
sumSq += (long)grid[i][j] * grid[i][j];
}
}
long diff = expectedSum - sum;
long diffSq = expectedSumSq - sumSq;
int b_plus_a = (int)(diffSq / diff);
int b = (int)((diff + b_plus_a) / 2);
int a = (int)(b + diff);
return new int[]{a, b};
}
}#include <vector>
using namespace std;
vector<int> findMissingAndRepeated(vector<vector<int>>& grid) {
int n = grid.size();
long long sum = 0, sumSq = 0;
long long expectedSum = ((long long)n * n * (n * n + 1)) / 2;
long long expectedSumSq = ((long long)n * n * (n * n + 1) * (2 * n * n + 1)) / 6;
for (const auto& row : grid) {
for (auto num : row) {
sum += num;
sumSq += (long long)num * num;
}
}
long long diff = expectedSum - sum;
long long diffSq = expectedSumSq - sumSq;
int b_plus_a = diffSq / diff;
int b = (diff + b_plus_a) / 2;
int a = b + diff;
return {a, b};
}function findMissingAndRepeated(grid) {
const n = grid.length;
let sum = 0, sumSq = 0;
const expectedSum = (n * n * (n * n + 1)) / 2;
const expectedSumSq = (n * n * (n * n + 1) * (2 * n * n + 1)) / 6;
for (const row of grid) {
for (const num of row) {
sum += num;
sumSq += num * num;
}
}
const diff = expectedSum - sum; // b - a
const diffSq = expectedSumSq - sumSq; // b^2 - a^2
const b_plus_a = diffSq / diff; // b + a
const b = (diff + b_plus_a) / 2;
const a = b + diff;
return [a, b];
}#include <stdio.h>
#include <stdlib.h>
int* findMissingAndRepeated(int** grid, int n, int* returnSize) {
long long sum = 0, sumSq = 0;
long long expectedSum = ((long long)n * n * (n * n + 1)) / 2;
long long expectedSumSq = ((long long)n * n * (n * n + 1) * (2 * n * n + 1)) / 6;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sum += grid[i][j];
sumSq += (long long)grid[i][j] * grid[i][j];
}
}
long long diff = expectedSum - sum; // b - a
long long diffSq = expectedSumSq - sumSq; // b^2 - a^2
int b_plus_a = diffSq / diff; // b + a
int b = (diff + b_plus_a) / 2;
int a = b + diff;
*returnSize = 2;
int *ans = (int*)malloc(2 * sizeof(int));
ans[0] = a;
ans[1] = b;
return ans;
}using System;
using System.Linq;
public class Solution {
public int[] FindMissingAndRepeated(int[][] grid) {
int n = grid.Length;
long sum = 0, sumSq = 0;
long expectedSum = ((long)n * n * (n * n + 1)) / 2;
long expectedSumSq = ((long)n * n * (n * n + 1) * (2 * n * n + 1)) / 6;
foreach (var row in grid) {
foreach (var num in row) {
sum += num;
sumSq += (long)num * num;
}
}
long diff = expectedSum - sum;
long diffSq = expectedSumSq - sumSq;
int b_plus_a = (int)(diffSq / diff);
int b = (int)((diff + b_plus_a) / 2);
int a = (int)(b + diff);
return new int[]{a, b};
}
}Using Python’s integer handling, perform calculations for the sums and use differential equations to determine missing and repeated numbers.
Time complexity is O(n^2); Space complexity is O(1).
Approach 3: Counting
We create an array cnt of length n^2 + 1 to count the frequency of each number in the matrix.
Next, we traverse i \in [1, n^2]. If cnt[i] = 2, then i is the duplicated number, and we set the first element of the answer to i. If cnt[i] = 0, then i is the missing number, and we set the second element of the answer to i.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the side length of the matrix.
function findMissingAndRepeatedValues(grid: number[][]): number[] {
const n = grid.length;
const cnt: number[] = Array(n * n + 1).fill(0);
const ans: number[] = Array(2).fill(0);
for (const row of grid) {
for (const x of row) {
if (++cnt[x] === 2) {
ans[0] = x;
}
}
}
for (let x = 1; ; ++x) {
if (cnt[x] === 0) {
ans[1] = x;
return ans;
}
}
}func findMissingAndRepeatedValues(grid [][]int) []int {
n := len(grid)
ans := make([]int, 2)
cnt := make([]int, n*n+1)
for _, row := range grid {
for _, x := range row {
cnt[x]++
if cnt[x] == 2 {
ans[0] = x
}
}
}
for x := 1; ; x++ {
if cnt[x] == 0 {
ans[1] = x
return ans
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Counting Frequency Approach | Time complexity: O(n^2), Space complexity: O(n^2) |
| Mathematical Summation Approach | Time complexity is O(n^2); Space complexity is O(1). |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Frequency | O(n²) | O(n²) | General case when extra memory is acceptable and you want the simplest implementation |
| Mathematical Summation | O(n²) | O(1) | When minimizing memory usage or demonstrating math-based optimization in interviews |
Frequently asked questions
Is Find Missing and Repeated Values easy or hard?
The problem is categorized as Easy because the direct frequency-count solution is straightforward. The mathematical summation approach adds a small twist but still relies on basic arithmetic and a single pass through the grid.
Find Missing and Repeated Values Python/Java solution
In Python or Java, iterate through the matrix and update a frequency array of size n² + 1. After counting, scan the array to find the value with count 2 (repeated) and count 0 (missing). The implementation runs in O(n²) time and is easy to translate across languages.
How to solve Find Missing and Repeated Values in O(n)?
The grid contains n² elements, so the effective linear complexity relative to the number of elements is O(n²). A single pass computes the sum and sum of squares, then algebra derives the missing and repeated numbers in constant extra space.
What is the best approach for Find Missing and Repeated Values?
The counting frequency approach is the most straightforward. Traverse the n x n matrix, count occurrences for values 1..n², and identify the number with frequency 2 (repeated) and the one with frequency 0 (missing). It runs in O(n²) time and uses O(n²) extra space.
Is Find Missing and Repeated Values asked at Google/Amazon/Meta?
Problems involving missing and duplicate numbers appear frequently in coding interviews at large tech companies. Variants of this question test array traversal, hash table usage, and mathematical reasoning, which are common topics in Google, Amazon, and Meta interview preparation.
What data structure is used in Find Missing and Repeated Values?
The most common structure is a frequency array or hash table that tracks how many times each value appears. Because the numbers range from 1 to n², an indexed array works efficiently with constant‑time updates and lookups.
What is the time complexity of Find Missing and Repeated Values?
Both common solutions run in O(n²) time because every cell in the matrix must be inspected. The counting method uses O(n²) extra space for the frequency array, while the mathematical summation approach reduces space complexity to O(1).