Beats 100% | Very Easy solution | C++ Java Python
IntuitionThe goal is to find the first index in the array arr such that marking the cells corresponding to the indices in arr completely fills either a row or a
![image.png](https://assets.leetcode.com/users/images/f5f1d724-4ce5-438f-99a9-fa1b4bc31e81_1737346193.8343136.png)
# Intuition
The goal is to find the first index in the array arr such that marking the cells corresponding to the indices in arr completely fills either a row or a column in the matrix mat. This is done by tracking the remaining unmarked cells in each row and column.

# Approach
1. Position Mapping:

    - First, map each value in the matrix mat to its corresponding position (row and column indices). This allows us to efficiently access the position of any value in constant time during traversal.
2. Tracking Row and Column Completion:

    - Maintain two arrays, rowSum and colSum, initialized to the size of the columns and rows respectively. These arrays represent how many unmarked cells are left in each row and column.
    - Initially, rowSum[j] = n for each column j, and colSum[i] = m for each row i, as no cells are marked at the beginning.
3. Simulate the Marking Process:

    - Iterate through the array arr, marking the corresponding cell in mat for each value.
    - Decrement the counts in the rowSum and colSum arrays for the respective row and column.
    - Check if the marking of the current cell completes a row (rowSum[y] == 0) or column (colSum[x] == 0). If so, return the index in arr as the result.
4. Edge Case:

    - If no row or column is completely filled by the end of the array, return -1.
# Complexity
- Time Complexity : O(n⋅m+len(arr)).
- Space Complexity : O(n⋅m).
# Code
```cpp []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n=mat.size(),m=mat[0].size();
        vector<int> position(n*m);
        vector<int> colSum(n,m),rowSum(m,n);
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                position[mat[i][j]-1] = i*m+j;
            }
        }
        for(int i=0; i<arr.size(); i++){
            int ind = position[arr[i]-1],
                x = ind/m, y = ind%m;
            
            rowSum[y]--;
            colSum[x]--;

            if(rowSum[y] == 0 || colSum[x] == 0) return i;
        }
        return -1;
    }
};
```
```Java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[] position = new int[n * m];
        int[] rowSum = new int[m];
        int[] colSum = new int[n];

        Arrays.fill(rowSum, n);
        Arrays.fill(colSum, m);

        // Map matrix values to their positions
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                position[mat[i][j] - 1] = i * m + j;
            }
        }

        // Process the marking based on arr
        for (int i = 0; i < arr.length; i++) {
            int ind = position[arr[i] - 1];
            int x = ind / m, y = ind % m;

            rowSum[y]--;
            colSum[x]--;

            if (rowSum[y] == 0 || colSum[x] == 0) {
                return i;
            }
        }
        return -1;
    }
}
```
```Python []
class Solution:
    def firstCompleteIndex(self, arr, mat):
        n, m = len(mat), len(mat[0])
        position = [0] * (n * m)
        rowSum = [n] * m
        colSum = [m] * n

        # Map matrix values to their positions
        for i in range(n):
            for j in range(m):
                position[mat[i][j] - 1] = i * m + j

        # Process the marking based on arr
        for i, value in enumerate(arr):
            ind = position[value - 1]
            x, y = divmod(ind, m)

            rowSum[y] -= 1
            colSum[x] -= 1

            if rowSum[y] == 0 or colSum[x] == 0:
                return i

        return -1

```
![Please hit the upvote button (1).png](https://assets.leetcode.com/users/images/6da7c2c9-1c0a-4eed-b6e6-14610ae5a2ec_1737346311.5625439.png)

['Array', 'Hash Table', 'Math', 'Matrix', 'Python', 'C++', 'Java']