Watch 10 video solutions for Find Missing and Repeated Values, a easy level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 8,516 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * nx that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members.x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members.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.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 | 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 |