We can follow these steps:

Approach

1. Pre-process the positions of elements:

   • First, we need to store the positions of the elements in the matrix. We can create a dictionary (position_map) that maps each value in the matrix to its (row, col) position.

2. Frequency Arrays:

   • We need two frequency arrays: one for the rows and one for the columns.
   • As we go through the arr array, we will increment the frequency of the respective row and column for each element.

3. Check for Complete Row or Column:

   • After each increment, check if any row or column becomes completely painted (i.e., its frequency reaches the size of the matrix's columns or rows).
   • If so, return the current index.

4. Return the result:

   • The index where either a row or column is fully painted is our answer.

Detailed Steps

1. Create a map position_map for each value in mat to its (row, col) position.
2. Create arrays row_count and col_count to track the number of painted cells in each row and column.
3. Traverse through arr and for each element, update the respective row and column counts.
4. If at any point a row or column is completely painted, return that index.

Let's implement this solution in PHP: 2661. First Completely Painted Row or Column

<?php
/**
 * @param Integer[] $arr
 * @param Integer[][] $mat
 * @return Integer
 */
function firstCompleteIndex($arr, $mat) {
    $m = count($mat);
    $n = count($mat[0]);
    
    // Step 1: Preprocess the positions of elements in the matrix
    $position_map = [];
    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            $position_map[$mat[$i][$j]] = [$i, $j];
        }
    }

    // Step 2: Initialize row and column counts
    $row_count = array_fill(0, $m, 0); // Frequency of painted cells in each row
    $col_count = array_fill(0, $n, 0); // Frequency of painted cells in each column

    // Step 3: Traverse arr and update counts
    foreach ($arr as $i => $value) {
        list($row, $col) = $position_map[$value];
        
        // Increment the row and column counts
        $row_count[$row]++;
        $col_count[$col]++;
        
        // Step 4: Check if any row or column is fully painted
        if ($row_count[$row] == $n || $col_count[$col] == $m) {
            return $i;
        }
    }

    // If no row or column is fully painted, return -1 (although the problem guarantees a solution)
    return -1;
}

// Example usage:
$arr = [1, 3, 4, 2];
$mat = [[1, 4], [2, 3]];
echo firstCompleteIndex($arr, $mat); // Output: 2

$arr = [2, 8, 7, 4, 1, 3, 5, 6, 9];
$mat = [[3, 2, 5], [1, 4, 6], [8, 7, 9]];
echo firstCompleteIndex($arr, $mat); // Output: 3
?>

Explanation:

1. Pre-processing positions:

   • We build a dictionary position_map where each value in mat is mapped to its (row, col) position. This helps in directly accessing the position of any value in constant time during the traversal of arr.

2. Frequency counts:

   • We initialize row_count and col_count arrays with zeros. These arrays will keep track of how many times a cell in a specific row or column has been painted.

3. Traversing the array:

   • For each value in arr, we look up its position in position_map, then increment the corresponding row and column counts.
   • After updating the counts, we check if any row or column has reached its full size (i.e., row_count[$row] == n or col_count[$col] == m). If so, we return the current index i.

4. Return Result:

   • The first index where either a row or column is completely painted is returned.

Time Complexity:

• Pre-processing: We build position_map in O(m * n).
• Traversal: We process each element of arr (which has a length of m * n), and for each element, we perform constant-time operations to update and check the row and column frequencies, which takes O(1) time.
• Overall, the time complexity is O(m * n).

Space Complexity:

• We store the positions of all elements in position_map, and we use O(m + n) space for the frequency arrays. Therefore, the space complexity is O(m * n).

This solution should efficiently handle the problem within the given constraints.