0ms |Beats 100% Proof | Using Hash Mapping with Simulation| Efficient & Easy C++ Solu| Full Explain
IntuitionThe task requires us to determine the smallest index i in the array arr such that either a row or a column in the matrix mat becomes completely painted

![20 Jan .jpg](https://assets.leetcode.com/users/images/fa149b64-f6f0-4de1-a249-b05e3611cbd2_1737339795.4005802.jpeg)



---




# Intuition
The task requires us to determine the smallest index `i` in the array `arr` such that either a row or a column in the matrix `mat` becomes completely painted.

- Each element in `arr` corresponds to a number in `mat` that gets painted in sequence.
- We can keep track of how many elements of each row and column are painted.
- The first time any row or column becomes fully painted, we return that index `i`.
<!-- Describe your first thoughts on how to solve this problem. -->

---



# Approach
**1. Mapping numbers in `mat` to their positions :**
Create mappings to quickly find the row and column indices of each number in the matrix. This avoids searching the matrix repeatedly.

- Use a `numToIndex` vector to map numbers from `mat` to their index in `arr`.
- Use `rowPos` and `colPos` arrays to store the row and column indices of each number in `mat`.

**2. Tracking painted cells :**
Maintain two arrays:

- `rowPainted` to track the number of painted cells in each row.
- `colPainted` to track the number of painted cells in each column.

**3. Simulating the painting process :**
Iterate through `arr`:

- For each number in `arr`, find its corresponding row and column indices using the mappings (`rowPos` and `colPos`).
- Increment the count for that row and column in `rowPainted` and `colPainted`.
- Check if the row or column is fully painted (count equals the number of cells in the row/column).

**4. Return the result :**
- The first index `i` where a row or column is completely painted is the answer.
<!-- Describe your approach to solving the problem. -->


---


# 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)$$ -->


---


![7e0e9898-f462-4965-b97f-f838ff5a6c18_1688759983.962739.jpeg](https://assets.leetcode.com/users/images/a1f42295-7e4e-4e58-8eaf-c47cd8e0ae01_1737339769.1375365.jpeg)


---



# Code
```cpp []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size(), N = m * n;
        vector<int> numToIndex(N + 1, -1);  
        for (int i = 0; i < N; ++i) {
            numToIndex[arr[i]] = i;
        }
        vector<int> rowPainted(m, 0), colPainted(n, 0);
        vector<int> rowPos(N), colPos(N);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int num = mat[i][j];
                int indexInArr = numToIndex[num];
                rowPos[indexInArr] = i;
                colPos[indexInArr] = j;
            }
        }
        for (int i = 0; i < N; ++i) {
            int num = arr[i];
            int rowIdx = rowPos[numToIndex[num]];
            int colIdx = colPos[numToIndex[num]];
            if (++rowPainted[rowIdx] == n || ++colPainted[colIdx] == m) {
                return i;
            }
        }

        return -1;
    }
};

```
['Array', 'Hash Table', 'Greedy', 'Matrix', 'Simulation', 'C++']