First Completely Painted Row or Column

Leetcode Problem:

• First Completely Painted Row or Column

Summary

• Find the smallest index at which either a row or a column will be completely painted in the matrix.

Approach

• The approach used is to first map the array elements to their corresponding indices in the matrix
• Then, for each row and column, find the maximum index that has been painted so far
• The smallest of these maximum indices is the smallest index at which either a row or a column will be completely painted.

Complexity

• O(m*n) where m is the number of rows and n is the number of columns in the matrix.

Explanation

• The solution code first creates a mapping of array elements to their corresponding indices in the matrix
• Then, for each row and column, it finds the maximum index that has been painted so far by iterating over the elements of the row or column
• The smallest of these maximum indices is the smallest index at which either a row or a column will be completely painted
• This approach ensures that all rows and columns are considered, and the smallest index is found.

Solution Code:

class Solution {
public:
    int vtoi[100001];
    int firstCompleteIndex(vector& arr, vector>& mat) {
        for(int i = 0 ; i < arr.size(); i++){
            vtoi[arr[i]] = i;
        }
        int m = mat.size();
        int n = mat[0].size();
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                mat[i][j] = vtoi[mat[i][j]];
            }
        }
        int ans = 100000;
        for(int i = 0 ; i < m; i++){
            int maxIdx = -1;
            for(int j = 0 ; j < n ; j++){
                maxIdx = max(maxIdx, mat[i][j]);
            }
            ans = min(ans, maxIdx);
        }
        for(int i = 0; i < n; i++){
            int maxIdx = -1;
            for(int j = 0; j < m; j++){
                maxIdx = max(maxIdx, mat[j][i]);
            }
            ans = min(ans, maxIdx);
        }
        return ans;
    }
};