Easy-to-understand✅✅ || Simple Hash Table Apprach 🚀🚀 || C++ 🔥🔥|| Java 🗿🗿 || Python3 💀💀
IntuitionThe problem asks us to find the smallest index i such that when we paint the cell corresponding to arr[i] in the matrix mat, a row or a column becomes
# Intuition
The problem asks us to find the smallest index $$i$$ such that when we paint the cell corresponding to $$arr[i]$$ in the matrix mat, a row or a column becomes completely painted. The matrix mat has all integers in the range $$[1, m*n]$$, and the array arr gives us the order in which these integers are painted.

The solution leverages efficient tracking of painted rows and columns while iterating through the numbers in arr. By marking rows and columns whenever a number is painted, we can easily detect when either a row or column becomes completely painted.

# Approach

- Store the position $$(i, j) $$of each number in the matrix mat using an array pos.

- Use a map $$m1$$ to count how many cells in each row and column are painted.
Keys: $${'R', i}$$ for rows and $${'C', j}$$ for columns.

- For each number in arr, find its position in mat using pos.
Increment the count for the corresponding row and column in m1.

- After each paint, check if the count of painted cells in the row equals the number of columns or in the column equals the number of rows.

- If a row or column is fully painted, return the current index.
If no row or column is fully painted, return $$-1$$.

# Complexity
- Time complexity: $$O(m*n + n*log(m*n))$$

- Space complexity: $$O(m*n)$$

# Code
```cpp []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n = arr.size();
        int row = mat.size(), col = mat[0].size();
        int index = 0;
        map<pair<char,int>, int> m1;
        vector<pair<int,int>> pos(row*col+1);
        for(int i=0;i<row;i++) {
            for(int j=0;j<col;j++) {
                pos[mat[i][j]] = {i, j};
            }
        }
        while(index<n) {
            auto curr = pos[arr[index]];
            int i = curr.first;
            int j = curr.second;
            m1[{'R',i}]++;
            m1[{'C',j}]++;
            if(m1[{'R',i}]==col || m1[{'C',j}]==row)
                return index;
            index++;
        }
        return -1;
    }
};
```

```java []
import java.util.*;

class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int n = arr.length;
        int row = mat.length, col = mat[0].length;
        int index = 0;
        Map<String, Integer> m1 = new HashMap<>();
        int[][] pos = new int[row * col + 1][2];
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                pos[mat[i][j]] = new int[]{i, j};
            }
        }
        
        while (index < n) {
            int[] curr = pos[arr[index]];
            int i = curr[0];
            int j = curr[1];
            m1.put("R" + i, m1.getOrDefault("R" + i, 0) + 1);
            m1.put("C" + j, m1.getOrDefault("C" + j, 0) + 1);
            if (m1.get("R" + i) == col || m1.get("C" + j) == row) {
                return index;
            }
            index++;
        }
        
        return -1;
    }
}
```

```python []
class Solution:
    def firstCompleteIndex(self, arr, mat):
        n = len(arr)
        row, col = len(mat), len(mat[0])
        index = 0
        m1 = {}
        pos = [[0, 0] for _ in range(row * col + 1)]
        
        for i in range(row):
            for j in range(col):
                pos[mat[i][j]] = [i, j]
        
        while index < n:
            i, j = pos[arr[index]]
            m1['R' + str(i)] = m1.get('R' + str(i), 0) + 1
            m1['C' + str(j)] = m1.get('C' + str(j), 0) + 1
            if m1['R' + str(i)] == col or m1['C' + str(j)] == row:
                return index
            index += 1
        
        return -1
```

![9c6061b0-baea-44aa-8210-a61340647c54.jpg](https://assets.leetcode.com/users/images/d5f96427-cc8c-4137-bfa1-9786388d19c0_1737353297.9736025.jpeg)



['Array', 'Hash Table', 'Matrix', 'Hash Function', 'Python', 'C++', 'Java', 'Python3']