✅ Easy to Understand | Hash Table | Java | C++ | Python | Detailed Video Explanation 🔥
IntuitionThe problem involves determining the first point in an array where marking an element leads to a complete row or column being filled in a matrix. My in
# Intuition
The problem involves determining the first point in an array where marking an element leads to a complete row or column being filled in a matrix. My initial thought was to map each element of the matrix to its respective coordinates, allowing quick access to the element's position. By maintaining counts of marked elements in each row and column, we can efficiently detect when a row or column is fully marked.

# Approach
1. **Mapping Matrix Elements**: 
   - Use a `HashMap` to store each element in the matrix as a key and its coordinates (row, column) as the value.
   - This allows for O(1) lookup of an element's position.

2. **Counting Marked Elements**:
   - Maintain two arrays, `rowc` and `colc`, to keep track of how many elements are marked in each row and column, respectively.

3. **Marking Process**:
   - Iterate through the input array `arr`, and for each element:
     - Retrieve its coordinates from the map.
     - Increment the count in the respective row and column.
     - Check if the current row or column is completely marked.
   - If a row or column becomes fully marked, return the current index in `arr`.

4. **Termination**:
   - If no row or column is fully marked after processing all elements, return `-1`.

# Complexity
- **Time complexity**:  
  - Creating the map: $$O(m \times n)$$, where $$m$$ is the number of rows and $$n$$ is the number of columns in the matrix.  
  - Processing the array `arr`: $$O(k)$$, where $$k$$ is the length of the array.  
  - Overall: $$O(m \times n + k)$$.

- **Space complexity**:  
  - The `HashMap` requires $$O(m \times n)$$ space to store the matrix elements.  
  - The `rowc` and `colc` arrays require $$O(m + n)$$ space.  
  - Overall: $$O(m \times n + m + n)$$.


# Code
```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        // Map to store the matrix elements as keys and their coordinates (row, column) as values
        Map<Integer, int[]> map = new HashMap<>();

        int m = mat.length;  // Number of rows in the matrix
        int n = mat[0].length;  // Number of columns in the matrix

        // Populate the map with matrix elements and their coordinates
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = mat[i][j];  // Matrix element
                int[] val = new int[]{i, j};  // Coordinates (row, column) of the element

                map.put(key, val);  // Store in the map
            }
        }

        // Arrays to count the number of elements marked in each row and column
        int[] rowc = new int[m];
        int[] colc = new int[n];

        // Iterate over the elements in the array
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];  // Current element being marked
            int[] loc = map.get(key);  // Retrieve the coordinates of the element from the map

            // Increment the count of marked elements in the respective row and column
            rowc[loc[0]]++;
            colc[loc[1]]++;

            // Check if the current row or column is fully marked
            if (rowc[loc[0]] == n || colc[loc[1]] == m) {
                return i;  // Return the current index if a row or column is completely marked
            }
        }

        // Impossible to come here as per problem constraints
        return -1;   
    }
}

```

```c++ []
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        unordered_map<int, pair<int, int>> map;

        int m = mat.size();     // Number of rows
        int n = mat[0].size();  // Number of columns

        // Populate the map with matrix elements and their coordinates
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[mat[i][j]] = {i, j};
            }
        }

        // Arrays to count the number of elements marked in each row and column
        vector<int> rowc(m, 0);
        vector<int> colc(n, 0);

        // Iterate over the elements in the array
        for (int i = 0; i < arr.size(); i++) {
            int key = arr[i];
            auto loc = map[key];  // Retrieve the coordinates of the element

            rowc[loc.first]++;
            colc[loc.second]++;

            // Check if the current row or column is fully marked
            if (rowc[loc.first] == n || colc[loc.second] == m) {
                return i;
            }
        }

        return -1;  // Return -1 if no row or column is fully marked
    }
};

```
```python []
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        unordered_map<int, pair<int, int>> map;

        int m = mat.size();     // Number of rows
        int n = mat[0].size();  // Number of columns

        // Populate the map with matrix elements and their coordinates
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[mat[i][j]] = {i, j};
            }
        }

        // Arrays to count the number of elements marked in each row and column
        vector<int> rowc(m, 0);
        vector<int> colc(n, 0);

        // Iterate over the elements in the array
        for (int i = 0; i < arr.size(); i++) {
            int key = arr[i];
            auto loc = map[key];  // Retrieve the coordinates of the element

            rowc[loc.first]++;
            colc[loc.second]++;

            // Check if the current row or column is fully marked
            if (rowc[loc.first] == n || colc[loc.second] == m) {
                return i;
            }
        }

        return -1;  // Return -1 if no row or column is fully marked
    }
};

```

LeetCode 2661 First Completely Painted Row or Column | Hash Table | Adobe Interview Question
https://youtu.be/6rY5YR0GOkU


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