3 passes -> 2 passes||C++3ms Py3 99.05%
IntuitionUse vector in stead of a hash map.
3 passes
2nd solution is 2 passes which is much simpler. both C++ & Python are implemented.Approach
Declare vector i
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Use vector in stead of a hash map.
3 passes
2nd solution is 2 passes which is much simpler. both C++ & Python are implemented.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Declare vector `idx(N+1)` where `N=m*n`
2. Use a loop to assign the values `idx[arr[i]]=i` for i
3. Need 2 correspondences for `pos=0,...,N-1` to its row index & its col index. So declare `to_i(N), to_j(N)`
4. In a double for loop assign the values
```
int pos=idx[mat[i][j]];
to_i[pos]=i;
to_j[pos]=j;
```
5. The 3rd pass is to find the answer. Declare `row(m), col(n)`.
6. Use a single loop to find the i:
```
int pos=idx[arr[i]];
// either row[..] or col[..] is full
if (++row[to_i[pos]]==n || ++col[to_j[pos]]==m) 
    return i;
```
7. 2nd approach is made which is much easier than 1st one. Just consider two mapping `to_i: mat[i][j] -> i & to_j: mat[i][j]-> j`
8. Python code is implemented.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(mn)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(mn)$$
# Code ||C++ 3 passes 4ms beats 95.12%
```cpp []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        const int m=mat.size(), n=mat[0].size(), N=m*n;
        vector<int> idx(N+1);
        for(int i=0; i<N; i++)
            idx[arr[i]]=i;

        vector<int> to_i(N), to_j(N);
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int pos=idx[mat[i][j]];
                to_i[pos]=i;
                to_j[pos]=j;
            }
        }
        vector<int> row(m), col(n);
        for(int i=0; i<N; i++){
            int pos=idx[arr[i]];
            if (++row[to_i[pos]]==n || ++col[to_j[pos]]==m) return i;
        }
        return -1;
    }
};
```
# 2 passes||C++ 3ms Beats 97.87%| Python 64ms beats 99.05%
```C++ []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        const int m=mat.size(), n=mat[0].size(), N=m*n;

        vector<int> to_i(N+1), to_j(N+1);
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int x=mat[i][j];
                to_i[x]=i;
                to_j[x]=j;
            }
        }
        vector<int> row(m), col(n);
        for(int i=0; i<N; i++){
            int x=arr[i];
            if (++row[to_i[x]]==n || ++col[to_j[x]]==m) return i;
        }
        return -1;
    }
};
```
```Python []
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n=len(mat), len(mat[0])
        N=m*n

        to_i=[-1]*(N+1)
        to_j=[-1]*(N+1)
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                to_i[x]=i
                to_j[x]=j
        R=[0]*m
        C=[0]*n
        for i, x in enumerate(arr):
            R[to_i[x]]+=1
            C[to_j[x]]+=1
            if R[to_i[x]]==n or C[to_j[x]]==m:
                return i
        return -1
```
['Array', 'Matrix', 'C++', 'Python3']