Problem
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
.
Examples
Example 1:
$$ \begin{array}{|c|c|} \hline \colorbox{Turquoise} 1 & 4 \\ \hline 2 & 3 \\ \hline \end{array}
\longrightarrow \begin{array}{|c|c|} \hline \colorbox{Turquoise} 1 & 4 \\ \hline 2 & \colorbox{Turquoise} 3 \\ \hline \end{array}
\longrightarrow \begin{array}{|c|c|} \hline \colorbox{Turquoise} 1 & \colorbox{Turquoise} 4 \\ \hline 2 & \colorbox{Turquoise} 3 \\ \hline \end{array} $$
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:
$$ \begin{array}{|c|c|c|} \hline 3 & \colorbox{Turquoise} 2 & 5 \\ \hline 1 & 4 & 6 \\ \hline 8 & 7 & 9 \\ \hline \end{array}
\longrightarrow \begin{array}{|c|c|c|} \hline 3 & \colorbox{Turquoise} 2 & 5 \\ \hline 1 & 4 & 6 \\ \hline \colorbox{Turquoise} 8 & 7 & 9 \\ \hline \end{array}
\longrightarrow \begin{array}{|c|c|c|} \hline 3 & \colorbox{Turquoise} 2 & 5 \\ \hline 1 & 4 & 6 \\ \hline \colorbox{Turquoise} 8 & \colorbox{Turquoise} 7 & 9 \\ \hline \end{array}
\longrightarrow \begin{array}{|c|c|c|} \hline 3 & \colorbox{Turquoise} 2 & 5 \\ \hline 1 & \colorbox{Turquoise} 4 & 6 \\ \hline \colorbox{Turquoise} 8 & \colorbox{Turquoise} 7 & 9 \\ \hline \end{array} $$
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].
$$ mat = \begin{array}{|c|c|c|} \hline 3 & 2 & 5 \\ \hline 1 & 4 & 6 \\ \hline 8 & 7 & 9 \\ \hline \end{array} $$
Constraints:
m == mat.length
n = mat[i].length
arr.length == m * n
1 <= m, n <= 10^5
1 <= m * n <= 1^05
1 <= arr[i], mat[r][c] <= m * n
- All the integers of
arr
are unique. - All the integers of
mat
are unique.
Solution
Method 1 - Using Hashtable and Count
To solve this problem, we need to perform the following steps:
- Traverse each element in
arr
and mark the corresponding cell inmat
as painted. - Check after each painting if any complete row or column is fully painted.
- Return the index at which a row or column is completely painted for the first time.
To implement this:
- Use two arrays to track the number of painted cells in each row and each column.
- Utilize a hashmap to store the positions of each number in
mat
for O(1) look-up time. - Iterate through
arr
and update the row and column counters. - Check if any row or column count reaches the respective row or column size after each update.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
Java
public class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length;
int n = mat[0].length;
// Mapping value positions in the matrix
int[][] pos = new int[m * n + 1][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
pos[mat[i][j]] = new int[]{i, j};
}
}
// Initialize row and column counters
int[] rowCount = new int[m];
int[] colCount = new int[n];
// Iterate and paint cells based on arr
for (int i = 0; i < arr.length; i++) {
int[] position = pos[arr[i]];
int row = position[0];
int col = position[1];
rowCount[row]++;
colCount[col]++;
// Check if row or column is completely painted
if (rowCount[row] == n || colCount[col] == m) {
return i;
}
}
return -1; // Should not reach here based on given constraint
}
}
Python
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
# Mapping value positions in the matrix
pos: Dict[int, Tuple[int, int]] = {}
for r in range(m):
for c in range(n):
pos[mat[r][c]] = (r, c)
# Initialize row and column counters
row_count: List[int] = [0] * m
col_count: List[int] = [0] * n
# Iterate and paint cells based on arr
for i, num in enumerate(arr):
r, c = pos[num]
row_count[r] += 1
col_count[c] += 1
# Check if row or column is completely painted
if row_count[r] == n or col_count[c] == m:
return i
return -1 # Should not reach here based on given constraint
Complexity
- ⏰ Time complexity:
O(m * n)
because we will iterate through all elements inarr
once, and the look-up and update operations are O(1) each. - 🧺 Space complexity:
O(m * n)
because we are using additional space to store the positions of the numbers and the counters for rows and columns.