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} $$

1
2
3

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} $$

1
2
3

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:

  1. Traverse each element in arr and mark the corresponding cell in mat as painted.
  2. Check after each painting if any complete row or column is fully painted.
  3. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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 in arr 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.