Skip to main content
Talentd

Find Missing and Repeated Values - Solution & Explanation

EasyArrayHash TableMathMatrix19 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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 <= 50
  • 1 <= grid[i][j] <= n * n
  • For all x that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members.
  • For all x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members.
  • For all x that 1 <= x <= n * n except two of them there is exatly one pair of i, j that 0 <= i, j <= n - 1 and grid[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'.

The C solution initializes a count array to track the frequency of each number. It iterates over the grid to populate the array, then checks which number has a frequency of 2 (repeated) and which has 0 (missing). The found values are returned as an array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n^2) due to iterating through the entire grid, and the space complexity is O(n^2) for the frequency array.

Try this approach in the editor →

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.

The C implementation computes the difference in sums and uses it to establish equations for a (repeated) and b (missing). Solving these provides the result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n^2) for iterating through the grid, space complexity is O(1) due to simple variable usage.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting Frequency Approach

The time complexity is O(n^2) due to iterating through the entire grid, and the space complexity is O(n^2) for the frequency array.

Mathematical Summation Approach

Time complexity is O(n^2) for iterating through the grid, space complexity is O(1) due to simple variable usage.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting FrequencyO(n²)O(n²)General case when extra memory is acceptable and you want the simplest implementation
Mathematical SummationO(n²)O(1)When minimizing memory usage or demonstrating math-based optimization in interviews

Video Solution

Find Missing and Repeated Values - Leetcode 2965 - Python • NeetCodeIO • 9,124 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Find Missing and Repeated Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays