Find Missing and Repeated Values

EASY

Description

You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n²]. 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

Checkout 4 different approaches to solve Find Missing and Repeated Values. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the counts and results, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Missing and Repeated Values. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Missing and Repeated Values

Patterns:

Math

Data Structures:

ArrayHash TableMatrix