First Completely Painted Row or Column - Solution Explanation and Code (Video Solution Available)
Video SolutionIntuitionThe problem involves identifying the first index in the array arr that completes a row or a column in the matrix mat. By mapping the matr
# Video Solution
[https://youtu.be/vejBP6zxtTY?si=kEPfeh8FK0Enzi_8]()
# Intuition
The problem involves identifying the first index in the array `arr` that completes a row or a column in the matrix `mat`. By mapping the matrix values to their coordinates, we can efficiently track the counts for rows and columns as we iterate through `arr`.

# Approach
1. Create a HashMap to store the coordinates of each value in the matrix `mat`. The key is the matrix value, and the value is an array representing the row and column indices.
2. Maintain two arrays, `row` and `col`, to track the count of marked cells for each row and column, respectively.
3. Iterate through the array `arr`:
   - For each value in `arr`, retrieve its coordinates from the HashMap.
   - Increment the corresponding row and column counts.
   - Check if the current row or column is fully marked. If so, return the current index.
4. If no row or column is fully marked after processing all elements of `arr`, return 1 as the default output.

# Complexity
- **Time complexity**: 
  - Building the HashMap: $$O(m \cdot n)$$, where $$m$$ is the number of rows and $$n$$ is the number of columns in `mat`.
  - Iterating through `arr`: $$O(k)$$, where $$k$$ is the length of `arr`.
  - Total: $$O(m \cdot n + k)$$.
- **Space complexity**: 
  - HashMap storage: $$O(m \cdot n)$$.
  - Additional arrays for row and column counts: $$O(m + n)$$.
  - Total: $$O(m \cdot n + m + n)$$.

# Code
```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        // HashMap to store the coordinates of each value in the matrix
        HashMap<Integer, int[]> map = new HashMap<>();
        // Arrays to track the count of marked cells for each row and column
        int[] row = new int[mat.length];
        int[] col = new int[mat[0].length];

        // Populate the HashMap with matrix value coordinates
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                int[] coordinate = new int[2];
                coordinate[0] = i;
                coordinate[1] = j;
                map.put(mat[i][j], coordinate);
            }
        }

        // Iterate through the array and track row/column completions
        for (int i = 0; i < arr.length; i++) {
            int[] coordinate = map.get(arr[i]);
            int r = coordinate[0];
            int c = coordinate[1];

            // Increment row and column counts
            row[r]++;
            col[c]++;

            // Check if the current row or column is fully marked
            if (row[r] == mat[0].length || col[c] == mat.length) {
                return i;
            }
        }

        // Default return value if no row/column is fully marked
        return 1;
    }
}
['Java']