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.
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:
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.
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.
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.
Time complexity is O(n^2) for iterating through the grid, space complexity is O(1) due to simple variable usage.
| Approach | Complexity |
|---|---|
| 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. |
| 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 |
Find Missing and Repeated Values - Leetcode 2965 - Python • NeetCodeIO • 8,516 views views
Watch 9 more video solutions →Practice Find Missing and Repeated Values with our built-in code editor and test cases.
Practice on FleetCode