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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Find the Missing and Repeating Number | 4 Approaches 🔥 • take U forward • 233,938 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