Optimizing Space | C++, Python (3-lines), Java
ApproachFirst we create an array/hashmap to map each value from [1,m⋅n] to a pair containing it's row and column index (r, c). Then we create two arrays rows an
# Approach
First we create an array/hashmap to map each value from $$[1, m \cdot n]$$ to a pair containing it's row and column index `(r, c)`. Then we create two arrays `rows` and `cols` of length $$m$$ and $n$ respectively. While itearting through `arr` we get the corresponding indices from our hashmap of pairs and then increment `rows[r]` and `cols[c]` and if `rows[r] == n` or `cols[c] == m` we return the index we're at $$i$$.

Only a slight optimization just for space is reusing the given array instead of creating 2 more arrays `rows` and `cols`. We can use the first row and column in `mat` to store our values intead. Note that since `mat[0][0]` is shared by both, I added an extra value to the end of the first row and 1-indexed the columns. Check the python code at the bottom for reducing the space complexity from $$O(mn + m + n)$$ to $$O(mn)$$.

# Complexity
- Time complexity: $$O(m \cdot n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(m \cdot 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();
        pair<int, int> map[arr.size() + 1];
        for (int r = 0; r < m; r++){
            for (int c = 0; c < n; c++){
                map[mat[r][c]] = {r, c + 1};
                mat[r][c] = 0;
            }
        }
        mat[0].push_back(0);
        for (int i = 0; i < arr.size(); i++){
            auto& [r, c] = map[arr[i]];
            if (++mat[r][0] == n || ++mat[0][c] == 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])
        map = {mat[r][c]: (r, c) for r in range(m) for c in range(n)}
        rows, cols = [0] * m, [0] * n
        for i in range(len(arr)):
            r, c = map[arr[i]]
            rows[r] += 1
            cols[c] += 1
            if rows[r] == n or cols[c] == m:
                return i
        return -1
```
```java []
class Solution {
    private class Pair{
        public int r, c;
        Pair(int r, int c) { this.r = r; this.c = c; }
    }
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Pair[] map = new Pair[arr.length + 1];
        for (int r = 0; r < m; r++){
            for (int c = 0; c < n; c++){
                map[mat[r][c]] = new Pair(r, c + 1);
                mat[r][c] = 0;
            }
        }
        mat[0] = new int[n + 1];
        for (int i = 0; i < arr.length; i++){
            int r = map[arr[i]].r, c = map[arr[i]].c;
            if (++mat[r][0] == n || ++mat[0][c] == m)
                return i;
        }
        return -1;
    }
}
```
## Python 3-lines
Here's a version that doesn't use extra space for the `rows` and `cols` arrays and instead gets the max index it would take to paint each row and column one by one by mapping the values in `arr` to their index. To put it simply the minimum index needed to entirely paint any specific row or column is the value that had the highest corresponding index in `arr`.
```python
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        map = {arr[i]: i for i in range(len(arr))}
        res = min(max(map[num] for num in row) for row in mat)
        return min(res, min(max(map[mat[r][c]] for r in range(len(mat))) for c in range(len(mat[0]))))
```
## C++
```cpp
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int k = arr.size(), map[k + 1], res = k;
        for (int i = 0; i < k; i++)
            map[arr[i]] = i;
        for (int r = 0; r < m; r++){
            int maxIndex = 0;
            for (int c = 0; c < n; c++){
                if (map[mat[r][c]] > maxIndex)
                    maxIndex = map[mat[r][c]];
            }
            if (maxIndex < res) res = maxIndex;
        }
        for (int c = 0; c < n; c++){
            int maxIndex = 0;
            for (int r = 0; r < m; r++){
                if (map[mat[r][c]] > maxIndex)
                    maxIndex = map[mat[r][c]];
            }
            if (maxIndex < res) res = maxIndex;
        }
        return res;
    }
};
```
['Array', 'Hash Table', 'C', 'Matrix', 'Python', 'C++', 'Java', 'Python3']