🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
IntuitionThe task is to find the first index in an array where marking a number in a given matrix results in a complete row or column being marked. My initial t
![image.png](https://assets.leetcode.com/users/images/7ba9b2f5-7b18-49ee-8b92-ff65df6f507c_1737359487.991835.png)



---


## Intuition
The task is to find the first index in an array where marking a number in a given matrix results in a complete row or column being marked. My initial thought is to track how many cells have been marked in each row and column, decrementing these counts as we process each number from the input array. Once a row or column reaches zero (indicating it has been fully marked), we can return the corresponding index.

## Approach
1. **Initialization**:
   - Determine the number of rows (`r`) and columns (`c`) in the matrix.
   - Create two lists (`row` and `col`) to keep track of how many cells are left to mark in each row and column, initialized to the total number of columns and rows, respectively.
   - Create a 2D list (`position`) to map each number in the matrix to its corresponding row and column indices.

2. **Mapping Positions**:
   - Populate the `position` list such that `position[number]` gives the coordinates of `number` in the matrix. This allows for quick lookups when processing the input array.

3. **Marking Cells**:
   - Iterate through the input array (`arr`):
     - For each number, retrieve its position from `position`.
     - Decrement the count for the corresponding row and column.
     - Check if either count reaches zero, indicating that the entire row or column has been marked.
     - If a complete row or column is found, return the current index.

4. **Return Value**:
   - If no complete row or column is found after processing all elements, return -1.

### Code Examples

```cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int r = mat.size();
        int c = mat[0].size();
        vector<int> row(r, c);
        vector<int> col(c, r);

        vector<vector<int>> position((r + 1) * (c + 1), vector<int>(2, 0));

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                position[mat[i][j]] = {i, j};
            }
        }

        int index = 0;
        for (int n : arr) {
            vector<int> pos = position[n];
            int rowIdx = pos[0];
            int colIdx = pos[1];

            row[rowIdx]--;
            col[colIdx]--;

            if (row[rowIdx] == 0 || col[colIdx] == 0) return index;

            index++;
        }
        return -1;
    }
};
```

```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int r = mat.length;
        int c = mat[0].length;
        int[] row = new int[r];
        int[] col = new int[c];
        
        // Initialize row and column counts
        Arrays.fill(row, c);
        Arrays.fill(col, r);
        
        // Map to find positions of numbers in the matrix
        int[][] position = new int[(r * c) + 1][2];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                position[mat[i][j]] = new int[]{i, j};
            }
        }

        for (int index = 0; index < arr.length; index++) {
            int number = arr[index];
            int[] pos = position[number];
            int rowIdx = pos[0];
            int colIdx = pos[1];

            // Decrement counts
            row[rowIdx]--;
            col[colIdx]--;

            // Check if any row or column is completely marked
            if (row[rowIdx] == 0 || col[colIdx] == 0) return index;
        }
        
        return -1; // If no complete row or column is found
    }
}
```

```javascript []
class Solution {
    firstCompleteIndex(arr, mat) {
        const r = mat.length;
        const c = mat[0].length;
        
        const row = new Array(r).fill(c);
        const col = new Array(c).fill(r);
        
        const position = Array.from({ length: (r * c) + 1 }, () => [0, 0]);

        for (let i = 0; i < r; i++) {
            for (let j = 0; j < c; j++) {
                position[mat[i][j]] = [i, j];
            }
        }

        for (let index = 0; index < arr.length; index++) {
            const number = arr[index];
            const [rowIdx, colIdx] = position[number];

            // Decrement counts
            row[rowIdx]--;
            col[colIdx]--;

            // Check if any row or column is completely marked
            if (row[rowIdx] === 0 || col[colIdx] === 0) return index;
        }

        return -1; // If no complete row or column is found
    }
}
```

```python []
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        r = len(mat)
        c = len(mat[0])
        
        # Initialize counters for rows and columns
        row_count = [c] * r
        col_count = [r] * c
        
        # Map to find positions of numbers in the matrix
        position_map = [[0, 0] for _ in range((r * c) + 1)]

        for i in range(r):
            for j in range(c):
                position_map[mat[i][j]] = [i, j]

        # Iterate through arr and mark cells
        for index in range(len(arr)):
            number = arr[index]
            pos = position_map[number]
            row_idx, col_idx = pos
            
            # Decrement counts
            row_count[row_idx] -= 1
            col_count[col_idx] -= 1
            
            # Check if any row or column is completely marked
            if row_count[row_idx] == 0 or col_count[col_idx] == 0:
                return index
        
        return -1  # If no complete row or column is found 
```

```dart []
class Solution {
  int firstCompleteIndex(List<int> arr, List<List<int>> mat) {
    int r = mat.length;
    int c = mat[0].length;

    List<int> row = List.generate(r, (index) => c);
    List<int> col = List.generate(c, (index) => r);

    List<List<int>> position =
      List.generate((r * c) + 1, (index) => [0, 0]);

    for (int i = 0; i < r; i++) {
      for (int j = 0; j < c; j++) {
          position[mat[i][j]] = [i, j];
      }
    }

    int index = 0;
    for (int n in arr) {
      List<int> pos = position[n];
      int rowIdx = pos[0];
      int colIdx = pos[1];

      // Decrement counts
      row[rowIdx]--;
      col[colIdx]--;

      // Check if any row or column is completely marked
      if (row[rowIdx] == 0 || col[colIdx] == 0) return index;

      index++;
    }
    
    return -1; // If no complete row or column is found 
  }
}
```

## Complexity

- **Time complexity**: $$O(n + m \times p)$$ where:
  - $$n$$ is the length of `arr`
  - $$m$$ is the number of rows in `mat`
  - $$p$$ is the number of columns in `mat`  
This accounts for constructing `positionMap` and iterating through `arr`.

- **Space complexity**: $$O(m \times p)$$ where:
  - $$m$$ is the number of rows in `mat`
  - $$p$$ is the number of columns in `mat`
This accounts for storing `positionMap`, `rowCount`, and `colCount`.

## Citations

**Counting Rows and Columns**: This resource covers various methods to count elements across different dimensions within data structures [LeetCode Discuss](https://leetcode.com/discuss/general-discussion/460694/).






---


![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}

['Array', 'Hash Table', 'C', 'Matrix', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']