Most Optimal Solution ✅Beats 100% | C++| Java | Python | JavaScript
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]IntuitionThe key insight is to track the painting progress of each row and column efficiently by
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

```cpp []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int row = mat.size();
        int col = mat[0].size();
        unordered_map<int, pair<int, int>> pos;
        
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                pos[mat[i][j]] = {i, j};
        
        vector<int> rCnt(row, 0);
        vector<int> cCnt(col, 0);
        
        for(int i = 0; i < arr.size(); i++) {
            auto [r, c] = pos[arr[i]];
            rCnt[r]++;
            cCnt[c]++;
            if(rCnt[r] == col || cCnt[c] == row)
                return i;
        }
        return arr.size() - 1;
    }
};
```
```python []
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        row = len(mat)
        col = len(mat[0])
        pos = {}
        
        for i in range(row):
            for j in range(col):
                pos[mat[i][j]] = (i, j)
        
        rCnt = [0] * row
        cCnt = [0] * col
        
        for i, val in enumerate(arr):
            r, c = pos[val]
            rCnt[r] += 1
            cCnt[c] += 1
            if rCnt[r] == col or cCnt[c] == row:
                return i
        return len(arr) - 1
```
```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        Map<Integer, int[]> pos = new HashMap<>();
        
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                pos.put(mat[i][j], new int[]{i, j});
        
        int[] rCnt = new int[row];
        int[] cCnt = new int[col];
        
        for(int i = 0; i < arr.length; i++) {
            int[] p = pos.get(arr[i]);
            rCnt[p[0]]++;
            cCnt[p[1]]++;
            if(rCnt[p[0]] == col || cCnt[p[1]] == row)
                return i;
        }
        return arr.length - 1;
    }
}
```
```javascript []
class Solution {
    firstCompleteIndex(arr, mat) {
        const row = mat.length;
        const col = mat[0].length;
        const pos = new Map();
        
        for(let i = 0; i < row; i++)
            for(let j = 0; j < col; j++)
                pos.set(mat[i][j], [i, j]);
        
        const rCnt = new Array(row).fill(0);
        const cCnt = new Array(col).fill(0);
        
        for(let i = 0; i < arr.length; i++) {
            const [r, c] = pos.get(arr[i]);
            rCnt[r]++;
            cCnt[c]++;
            if(rCnt[r] === col || cCnt[c] === row)
                return i;
        }
        return arr.length - 1;
    }
}
```
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The key insight is to track the painting progress of each row and column efficiently by using a hashmap to store positions and counter arrays.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Create a hashmap to store positions of numbers in matrix
2. Use two arrays to count painted cells in each row and column
3. For each number in arr:
   - Get its position from hashmap
   - Increment row and column counts
   - Check if any row or column is complete

# Complexity
- Time complexity: $$O(m*n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
- Space complexity: $$O(m*n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
### *If you have any questions or need further clarification, feel free to drop a comment! 😊*
['Array', 'Hash Table', 'Matrix', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']