Scale Engineer

Find Missing and Repeated Values

Easy
#2645Time: 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.
Patterns
Math
Data structures
ArrayHash TableMatrix

Prompt

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 <= 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 exactly one pair of i, j that 0 <= i, j <= n - 1 and grid[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, repeated and missing, to store the results.
  • Iterate through each number k from 1 to n*n.
  • For each k, initialize a count to 0.
  • Traverse the entire grid to count the occurrences of k.
  • After counting, check the value of count:
    • If count is 2, then k is the repeated number. Store it in repeated.
    • If count is 0, then k is the missing number. Store it in missing.
  • Once both repeated and missing are 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

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.

← Previous

Previous problem

Next →

Next problem