Find Missing and Repeated Values

Leetcode Problem:

• Find Missing and Repeated Values

Summary

• Find the repeating and missing numbers in a 2D grid.

Approach

• Use a boolean array to track the presence of each number in the grid, then iterate through the array to find the repeating and missing numbers.

Complexity

• O(n^2) where n is the size of the grid

Explanation

• The solution first initializes a boolean array 'appear' of size n*n+1 to track the presence of each number
• It then iterates through the grid, setting the corresponding index in the 'appear' array to true for each number
• After that, it iterates through the 'appear' array and adds the index that is still false to the result vector
• This process finds the missing number
• The repeating number is found by iterating through the grid and adding the number to the result vector if it is already set to true in the 'appear' array.

Solution Code:

class Solution {
public:
    bool appear[2501] = {false,};
    vector findMissingAndRepeatedValues(vector>& grid) {
        int N = grid.size();
        vector ans;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(appear[grid[i][j]]){
                    ans.push_back(grid[i][j]);
                }
                appear[grid[i][j]] = true;
            }
        }
        for(int i = 1 ; i <= N*N; i++){
            if(!appear[i]){
                ans.push_back(i);
                return ans;
            }

        }
        return ans;
    }
};