🎯Easy || C++ || Python || Java ||✨Hash Table ||👌Beginner-Friendly
IntuitionThe idea behind this solution is to determine the first index in the array arr that completes either a row or a column in the matrix mat. Completion of
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The idea behind this solution is to determine the first index in the array arr that completes either a row or a column in the matrix mat. Completion of a row or column means that all elements in that row or column have been seen in the sequence up to that index.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Mapping Matrix Elements to Their Positions: Use an unordered map (`mp`) to store the positions (row and column indices) of each element in the matrix `mat`.

2. Count Down Rows and Columns: Maintain two vectors, `r` and `c`, to track the remaining unvisited elements in each row and column, respectively.

3. Iterate Through arr: For each element in the array `arr`, decrement the corresponding `row` and `column` counts. If any row or column count reaches zero, that means the row or column is fully covered, and we return the current index.
# Complexity
- Time complexity: $$O(m \times n)$$ to populate the map and $$O(k)$$ to iterate through the array arr, where m is the number of rows, n is the number of columns, and k is the size of arr. Overall, the time complexity is $$O(m \times n + k)$$.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(m \times n)$$ for storing positions in the map, and $$O(m + n)$$ for the row and column count vectors. Overall, the space complexity is $$O(m \times n)$$.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```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>> mp;
        vector<int> r(m,n), c(n,m);
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                mp[mat[i][j]] = {i,j};
        for(int i=0;i<arr.size();i++){
            auto [row, col] = mp[arr[i]];
            if(--r[row]==0 || --c[col]==0) return i;
        }
        return -1;
    }
};
```
```python []
from typing import List, Tuple
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        mp = {}
        r = [n] * m
        c = [m] * n
        
        for i in range(m):
            for j in range(n):
                mp[mat[i][j]] = (i, j)
        
        for i in range(len(arr)):
            row, col = mp[arr[i]]
            if r[row] - 1 == 0 or c[col] - 1 == 0:
                return i
            r[row] -= 1
            c[col] -= 1
        
        return -1
```
```java []
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Map<Integer, int[]> mp = new HashMap<>();
        int[] r = new int[m];
        int[] c = new int[n];
        
        for(int i = 0; i < m; i++) {
            r[i] = n;
        }
        for(int i = 0; i < n; i++) {
            c[i] = m;
        }
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                mp.put(mat[i][j], new int[]{i, j});
            }
        }
        
        for(int i = 0; i < arr.length; i++) {
            int[] pos = mp.get(arr[i]);
            int row = pos[0], col = pos[1];
            r[row]--;
            c[col]--;
            if(r[row] == 0 || c[col] == 0) return i;
        }
        
        return -1;
    }
}
```
['Array', 'Hash Table', 'Matrix', 'C++', 'Java', 'Python3']