Find Missing and Repeated Values
EasyPrompt
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 * n- For all
xthat1 <= x <= n * nthere is exactly onexthat is not equal to any of the grid members. - For all
xthat1 <= x <= n * nthere is exactly onexthat is equal to exactly two of the grid members. - For all
xthat1 <= x <= n * nexcept two of them there is exactly one pair ofi, jthat0 <= i, j <= n - 1andgrid[i][j] == x.
Approaches
4 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible number that could be in the grid (from 1 to n²) and, for each of these numbers, iterating through the entire grid to count how many times it appears. This allows us to identify which number appears twice and which number appears zero times.
Algorithm
- Initialize two variables,
repeatedandmissing, to store the results. - Iterate through each number
kfrom 1 ton*n. - For each
k, initialize acountto 0. - Traverse the entire
gridto count the occurrences ofk. - After counting, check the value of
count:- If
countis 2, thenkis the repeated number. Store it inrepeated. - If
countis 0, thenkis the missing number. Store it inmissing.
- If
- Once both
repeatedandmissingare found, you can break the loops. - Return the
[repeated, missing]array.
Walkthrough
This method systematically checks every candidate number against every element in the grid. We loop from k = 1 to n*n. In each iteration of this outer loop, we perform a full scan of the n x n grid. During the scan, we count how many times the number k is present. According to the problem statement, one number will have a count of 2 (the repeated one), one will have a count of 0 (the missing one), and all others will have a count of 1. We store these numbers when we find them and return the result.
class Solution { public int[] findMissingAndRepeatedValues(int[][] grid) { int n = grid.length; int repeated = -1, missing = -1; for (int k = 1; k <= n * n; k++) { int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == k) { count++; } } } if (count == 2) { repeated = k; } if (count == 0) { missing = k; } } return new int[]{repeated, missing}; }}Complexity
Time
O(n⁴), where n is the dimension of the grid. The outer loop runs n² times, and for each iteration, we traverse the n x n grid, which takes n² operations. This results in a total complexity of O(n² * n²) = O(n⁴).
Space
O(1), as we only use a few variables to store the counts and results, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space (O(1) space complexity).
Cons
Extremely inefficient due to the nested loops.
Not a practical solution for the given constraints, and would likely time out in a coding platform environment.
Solutions
Solution
class Solution {public int[] findMissingAndRepeatedValues(int[][] grid) { int n = grid.length; int[] cnt = new int[n * n + 1]; int[] ans = new int[2]; for (int[] row : grid) { for (int x : row) { if (++cnt[x] == 2) { ans[0] = x; } } } for (int x = 1;; ++x) { if (cnt[x] == 0) { ans[1] = x; return ans; } } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.