✅🔥Beating  99.5% | 🔥BRUTEFORCE → OPTIMAL🔥| Detailed Expiation✅
Intuition

The goal is to find the first index in the array arr such that a row or column in the matrix mat is completely marked (or filled).


The problem revo
# Intuition
- The goal is to find the first index in the array arr such that a row or column in the matrix mat is completely marked (or filled).

- The problem revolves around efficiently marking matrix cells and checking the row/column completion condition.

# BRUTEFORCE$$ [TLE]$$
1. Iterate over the elements of arr.
2. Find the position of the current element in mat using a nested loop.
3. Mark the corresponding position in mat as visited (e.g., -1).
4. After marking, check if the row or column of the marked cell is fully visited.
5. If yes, return the index in arr.

# Complexity
- Time complexity: $$ O(N×M×N×M)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(1)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public boolean checkRowCol(int[][] mat, int r, int c)
    {
        int r1 = 0, c1=0;
        for(;r1<mat.length; r1++)
            if(mat[r1][c]!=-1)
                break;
        if(r1==mat.length) return true;
        for(;c1<mat[0].length; c1++)
            if(mat[r][c1]!=-1)
                break;
        return c1==mat[0].length;
    }
    public int[] markIndex(int ele,int[][] mat)
    {
        for(int i=0; i<mat.length; i++)
        {
            for(int j=0; j<mat[i].length; j++)
            {
                if(mat[i][j]==ele)
                    return new int[]{i,j};
            }
        }
        return new int[]{0,0};
    }
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        for(int i=0; i<arr.length; i++)
        {
            int[] ind = markIndex(arr[i],mat);
            mat[ind[0]][ind[1]] = -1;
            if(checkRowCol(mat,ind[0],ind[1])) return i; 
        }
        return 0;
    }
}
```

# OPTIMAL
1. Preprocess the mat to create mappings (row and col) from matrix values to their row/column indices.
2. Use arrays rowCount and colCount to track the count of marked cells in each row and column.
3. For each element in arr, directly locate its row and column using the preprocessed mappings.
4. Update the counters for the respective row and column, and return the index if a row or column is fully marked.

# Complexity
- Time complexity: $$ O(N×M)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(N×M)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[] rowCount = new int[n];
        int[] colCount = new int[m];
        int[] row= new int[m*n+1];
        int[] col = new int[m*n+1];
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                row[mat[i][j]] = i;
                col[mat[i][j]] = j;
            }
        }        
        for(int i=0; i<m*n; i++)
        {
            int ele = arr[i];
            int r = row[ele];
            int c = col[ele];
            rowCount[r]++;
            colCount[c]++;
            if(rowCount[r]==m || colCount[c]==n) return i;
        }
        return 0;
    }
}
```

['Hash Table', 'Matrix', 'Java']