2661

2661. First Completely Painted Row or Column (Medium)

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

 

Example 1:

Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]
Output: 2
Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2:

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Output: 3
Explanation: The second column becomes fully painted at arr[3].

 

Constraints:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 105
• 1 <= m * n <= 105
• 1 <= arr[i], mat[r][c] <= m * n
• All the integers of arr are unique.
• All the integers of mat are unique.

Companies: Citadel

Related Topics:
Array, Hash Table, Matrix

Similar Questions:

• Check if Every Row and Column Contains All Numbers (Easy)
• Difference Between Ones and Zeros in Row and Column (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/first-completely-painted-row-or-column
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int firstCompleteIndex(vector<int>& A, vector<vector<int>>& M) {
        int m = M.size(), n = M[0].size();
        vector<int> row(m), col(n);
        vector<pair<int, int>> index(A.size() + 1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                index[M[i][j]] = {i, j};
            }
        }
        for (int i = 0; i < A.size(); ++i) {
            auto &[x, y] = index[A[i]];
            if (++row[x] == n || ++col[y] == m) return i;
        }
        return -1;
    }
};