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

Description Solution Video 7:34

2965. Find Missing and Repeated Values

Easy83.2% acceptance6 companies

You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n²]. 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.

Asked at 6 companies

Bloomberg

Google Amazon Microsoft Zoho Meta

Topics

7:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,3],[2,2]]

Input

[[9,1,7],[8,9,2],[3,4,6]]

Your code is saved on this device.Solution