2661. First Completely Painted Row or Column LeetCode Solution
In this guide, you will get 2661. First Completely Painted Row or Column LeetCode Solution with the best time and space complexity. The solution to First Completely Painted Row or Column problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of First Completely Painted Row or Column
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.
2661. First Completely Painted Row or Column LeetCode Solution in C++
class Solution {
public:
int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
const int m = mat.size();
const int n = mat[0].size();
// rows[i] := the number of painted grid in the i-th row
vector<int> rows(m);
// cols[j] := the number of painted grid in the j-th column
vector<int> cols(n);
// numToRow[num] := the i-th row of `num` in `mat`
vector<int> numToRow(m * n + 1);
// numToCol[num] := the j-th column of `num` in `mat`
vector<int> numToCol(m * n + 1);
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
numToRow[mat[i][j]] = i;
numToCol[mat[i][j]] = j;
}
for (int i = 0; i < arr.size(); ++i) {
if (++rows[numToRow[arr[i]]] == n)
return i;
if (++cols[numToCol[arr[i]]] == m)
return i;
}
throw;
}
}; /* code provided by PROGIEZ */
2661. First Completely Painted Row or Column LeetCode Solution in Java
class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
final int m = mat.length;
final int n = mat[0].length;
// rows[i] := the number of painted grid in the i-th row
int[] rows = new int[m];
// cols[j] := the number of painted grid in the j-th column
int[] cols = new int[n];
// numToRow[num] := the i-th row of `num` in `mat`
int[] numToRow = new int[m * n + 1];
// numToCol[num] := the j-th column of `num` in `mat`
int[] numToCol = new int[m * n + 1];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
numToRow[mat[i][j]] = i;
numToCol[mat[i][j]] = j;
}
for (int i = 0; i < arr.length; ++i) {
if (++rows[numToRow[arr[i]]] == n)
return i;
if (++cols[numToCol[arr[i]]] == m)
return i;
}
throw new IllegalArgumentException();
}
} // code provided by PROGIEZ
2661. First Completely Painted Row or Column LeetCode Solution in Python
class Solution:
def firstCompleteIndex(self, arr: list[int], mat: list[list[int]]) -> int:
m = len(mat)
n = len(mat[0])
# rows[i] := the number of painted grid in the i-th row
rows = [0] * m
# cols[j] := the number of painted grid in the j-th column
cols = [0] * n
# numToRow[num] := the i-th row of `num` in `mat`
numToRow = [0] * (m * n + 1)
# numToCol[num] := the j-th column of `num` in `mat`
numToCol = [0] * (m * n + 1)
for i, row in enumerate(mat):
for j, num in enumerate(row):
numToRow[num] = i
numToCol[num] = j
for i, a in enumerate(arr):
rows[numToRow[a]] += 1
if rows[numToRow[a]] == n:
return i
cols[numToCol[a]] += 1
if cols[numToCol[a]] == m:
return i # code by PROGIEZ
