# First Completely Painted Row or Column
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/first-completely-painted-row-or-column)
Canonical: https://scaleengineer.com/dsa/problems/first-completely-painted-row-or-column
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## 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`.

**Example 1:**

![](image explanation for example 1)![image explanation for example 1](https://assets.glich.co/dsa/first-completely-painted-row-or-column/image1.jpg) 

**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:**

![image explanation for example 2](https://assets.glich.co/dsa/first-completely-painted-row-or-column/image2.jpg) 

**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**.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. For each number in `arr`, we perform a full scan of the matrix `mat` to find its location. We use an auxiliary boolean matrix to keep track of which cells have been painted. After painting a cell, we check its entire row and column to see if they have become completely painted.
**Time:** O((m*n)^2). The outer loop runs up to `k` times (where `k` is the answer index, worst case `m*n`). Inside the loop, searching the matrix takes O(m*n). This results in a total complexity of O(k * m * n), which is O((m*n)^2) in the worst case. · **Space:** O(m * n) to store the `painted` boolean matrix.
**Pros:** Simple to conceptualize and implement.; Uses a straightforward simulation of the problem statement.
**Cons:** Extremely inefficient due to repeated searching of the matrix.; Will result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
The brute-force method involves iterating through each element of the `arr`. In each iteration, we take the number and search for it within the `mat`. This search operation itself takes O(m*n) time. Once found at `(r, c)`, we mark this position in a separate `painted` grid. Then, we check if row `r` is complete by scanning all `n` cells in that row, and similarly, check column `c` by scanning all `m` cells. This entire process (search, mark, check) is repeated for each number in `arr` until a complete row or column is found.

```java
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        boolean[][] painted = new boolean[m][n];

        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            int r = -1, c = -1;

            // Find val in mat
            find_val: for (int row = 0; row < m; row++) {
                for (int col = 0; col < n; col++) {
                    if (mat[row][col] == val) {
                        r = row;
                        c = col;
                        break find_val;
                    }
                }
            }

            painted[r][c] = true;

            // Check row r
            boolean rowComplete = true;
            for (int col = 0; col < n; col++) {
                if (!painted[r][col]) {
                    rowComplete = false;
                    break;
                }
            }
            if (rowComplete) {
                return i;
            }

            // Check column c
            boolean colComplete = true;
            for (int row = 0; row < m; row++) {
                if (!painted[row][c]) {
                    colComplete = false;
                    break;
                }
            }
            if (colComplete) {
                return i;
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Create a boolean matrix `painted` of the same dimensions as `mat`, initialized to `false`.
- Iterate through the input array `arr` from index `i = 0` to `arr.length - 1`.
- For each number `val = arr[i]`:
  - Search the entire `mat` to find the row `r` and column `c` where `mat[r][c] == val`.
  - Mark the cell as painted by setting `painted[r][c] = true`.
  - Check if the entire row `r` is painted by iterating through its columns.
  - If the row is complete, return `i`.
  - Check if the entire column `c` is painted by iterating through its rows.
  - If the column is complete, return `i`.

## Simulation with Position Pre-computation
This approach improves upon the brute-force method by optimizing the search for each number's location. We first pre-process `mat` to store the coordinates of every number in a hash map or an array. This allows for an O(1) lookup of a number's position. The rest of the simulation, which involves marking cells in a boolean grid and then checking the entire row and column for completion, remains the same.
**Time:** O(m*n * (m+n)). Pre-computation takes O(m*n). The main loop runs up to `k` times (worst case `m*n`). Inside, checking the row and column takes O(m+n). Total time is O(m*n + k*(m+n)). · **Space:** O(m * n) for the `positions` map and the `painted` matrix.
**Pros:** Faster than the pure brute-force approach.; Eliminates the expensive O(m*n) search from the main loop.
**Cons:** The check for a completed row or column is still inefficient.; Can still be too slow for constraints where one dimension is very large (e.g., m=10^5, n=1).
### Explanation
To avoid the costly O(m*n) search in every step, we can pre-compute the locations of all numbers. We create a map where keys are the numbers from `mat` and values are their `(row, col)` coordinates. This pre-computation takes O(m*n) time. After this, we iterate through `arr`. For each number, we get its coordinates in O(1) from our map. We then mark it in a `painted` boolean grid and perform the same O(m+n) check on the corresponding row and column to see if they are full.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        
        Map<Integer, int[]> posMap = new HashMap<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                posMap.put(mat[r][c], new int[]{r, c});
            }
        }

        boolean[][] painted = new boolean[m][n];

        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            int[] pos = posMap.get(val);
            int r = pos[0];
            int c = pos[1];

            painted[r][c] = true;

            // Check row r
            boolean rowComplete = true;
            for (int col = 0; col < n; col++) {
                if (!painted[r][col]) {
                    rowComplete = false;
                    break;
                }
            }
            if (rowComplete) {
                return i;
            }

            // Check column c
            boolean colComplete = true;
            for (int row = 0; row < m; row++) {
                if (!painted[row][c]) {
                    colComplete = false;
                    break;
                }
            }
            if (colComplete) {
                return i;
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Create a map or an array `positions` to store the coordinates of each number in `mat`.
- Populate `positions` by iterating through `mat` once.
- Initialize a boolean matrix `painted` of size `m x n` to all `false`.
- Iterate through `arr` with index `i`.
- For each number `val = arr[i]`:
  - Get its coordinates `(r, c)` from `positions` in O(1) time.
  - Set `painted[r][c] = true`.
  - Check the entire row `r` and column `c` in the `painted` matrix for completion.
  - If either is complete, return `i`.

## Optimal Approach with Position Map and Counters
This is the most efficient approach. It optimizes both finding the number's location and checking for completion. Like the previous approach, it uses a data structure for O(1) position lookups. The key improvement is using two counter arrays, one for rows and one for columns. When a cell `(r, c)` is painted, we simply increment the counters for row `r` and column `c`. A row `r` is complete if its counter reaches `n` (the number of columns), and a column `c` is complete if its counter reaches `m` (the number of rows). This makes the check an O(1) operation.
**Time:** O(m * n). The pre-computation step to build the `positions` map takes O(m*n). The main loop iterates through `arr` once (at most `m*n` times), and each step inside the loop is an O(1) operation. Therefore, the total time complexity is linear with respect to the number of cells in the matrix. · **Space:** O(m * n). We need O(m*n) space for the `positions` array, O(m) for `rowCount`, and O(n) for `colCount`. The dominant term is O(m*n).
**Pros:** Highly efficient with linear time complexity.; All operations inside the main loop are O(1).; Passes all constraints comfortably.
**Cons:** Requires extra space for the position map and counter arrays, which is proportional to the size of the matrix.
### Explanation
This optimal solution begins by pre-calculating the position of each number in the matrix and storing it in a `positions` array for O(1) lookup. Since the numbers are guaranteed to be in the range `[1, m*n]`, an array is more efficient than a hash map. We also initialize two arrays, `rowCount` and `colCount`, to keep track of the number of painted cells in each row and column, respectively.

Then, we iterate through `arr`. For each number, we find its row `r` and column `c` using our `positions` array. We increment `rowCount[r]` and `colCount[c]`. After each increment, we check if `rowCount[r]` has reached `n` (the total number of columns) or if `colCount[c]` has reached `m` (the total number of rows). The first time this condition is met, we have found the first completely painted row or column, and we return the current index `i`.

```java
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        
        // Using an array for positions since values are 1 to m*n
        int[][] pos = new int[m * n + 1][2];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                pos[mat[r][c]][0] = r;
                pos[mat[r][c]][1] = c;
            }
        }

        int[] rowCount = new int[m];
        int[] colCount = new int[n];

        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            int r = pos[val][0];
            int c = pos[val][1];

            rowCount[r]++;
            colCount[c]++;

            if (rowCount[r] == n || colCount[c] == m) {
                return i;
            }
        }
        
        return -1; // Should not be reached as a solution always exists
    }
}
```
### Algorithm
- Create an array `positions` of size `m*n + 1` to store the coordinates of each number.
- Populate `positions` by iterating through `mat`: `positions[mat[r][c]] = {r, c}`.
- Initialize a row counter array `rowCount` of size `m` and a column counter array `colCount` of size `n` to all zeros.
- Iterate through `arr` with index `i`.
- For each number `val = arr[i]`:
  - Get coordinates `(r, c)` from `positions[val]`.
  - Increment `rowCount[r]` and `colCount[c]`.
  - Check if `rowCount[r] == n` or `colCount[c] == m`.
  - If either condition is true, return `i`.

# Solutions
### Java

```java
class Solution {
public
  int firstCompleteIndex(int[] arr, int[][] mat) {
    int m = mat.length, n = mat[0].length;
    Map<Integer, int[]> idx = new HashMap<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        idx.put(mat[i][j], new int[]{i, j});
      }
    }
    int[] row = new int[m];
    int[] col = new int[n];
    for (int k = 0;; ++k) {
      var x = idx.get(arr[k]);
      int i = x[0], j = x[1];
      ++row[i];
      ++col[j];
      if (row[i] == n || col[j] == m) {
        return k;
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int firstCompleteIndex(vector<int> &arr, vector<vector<int>> &mat) {
    int m = mat.size(), n = mat[0].size();
    unordered_map<int, pair<int, int>> idx;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        idx[mat[i][j]] = {i, j};
      }
    }
    vector<int> row(m), col(n);
    for (int k = 0;; ++k) {
      auto [i, j] = idx[arr[k]];
      ++row[i];
      ++col[j];
      if (row[i] == n || col[j] == m) {
        return k;
      }
    }
  }
};

```

### Python

```python
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int: m, n = len(mat), len(mat[0]) idx = {} for i in range(m): for j in range(n): idx[mat[i][j]] = (i, j) row = [0] * m col = [0] * n for k in range(len(arr)): i, j = idx[arr[k]] row[i] += 1 col[j] += 1 if row[i] == n or col[j] == m: return k

```