Map with Optimized Checking - O(N*M)
SolutionOverviewWe are given an m×n matrix mat and an array arr of length m∗n both containing every integer from [1,m∗n].Starting from index i = 0, mark the val
# Solution

---

## Overview

We are given an $m \times n$ matrix `mat` and an array `arr` of length $m * n$ both containing every integer from $[1, m * n]$.

Starting from index `i = 0`, mark the value `arr[i]` as seen in `mat`. Return the smallest index where either a row or column is fully seen. 

---

## Approach 1: Map with Brute Force Checking (TLE)

### Intuition

Starting from index `i = 0`, we mark the value `arr[i]` as seen in `mat`. To be more efficient, we use a map to get the row and column of the value in `mat`. 

To mark the value `arr[i]` as seen, we multiply `arr[i]` by $-1$. Now if any row or column is completely seen, we can return the current index $i$. We only need to check the row and column that `arr[i]` is in, because this is the only row and column that is being modified at this iteration. If any value in the row or column is positive, this means we have not seen the full row or column yet.

### Algorithm

- Initialize `R` as the number of rows and `C` as the number of columms in `mat` and initialize a map `m`
- For all rows `row` and all columns `col`, set the value `mat[row][col]`  to the position `[row, column]` in the map `m`
- For every index $i$:
    - Let `value` be the value of `arr[i]`
    - Get the row and column index, `row` and `col` from `m`, that is, `m[value]`
    - Mark the row and column as seen, that is, `mat[row][col] = -mat[row][col]`
    - If the row or column is fully seen:
        - Return $i$

### Implementation

```python3 []
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        def checkRow(row: int) -> bool:
            """ return true if row is completely seen """
            for col in range(C):
                if mat[row][col] > 0:
                    return False
            return True

        def checkColumn(col: int) -> bool:
            """ return true if col is completely seen """
            for row in range(R):
                if mat[row][col] > 0:
                    return False
            return True

        R, C = len(mat), len(mat[0])
        m = {}
        for row in range(R):
            for col in range(C):
                value = mat[row][col]
                m[value] = [row, col]

        for index, val in enumerate(arr):
            row, col = m[val]
            mat[row][col] = -mat[row][col] # mark as seen
            if checkRow(row) or checkColumn(col): # if completely seen
                return index
        return -1        
```
```C++ []
class Solution {
public:
    bool checkRow(int row, vector<vector<int>>& mat) {
        // return true if row is completely seen
        for (int col = 0; col < mat[0].size(); col++) {
            if (mat[row][col] > 0) {
                return false;
            }
        }
        return true;
    }
    bool checkColumn(int col, vector<vector<int>>& mat) {
        // return true if col is completely seen
        for (int row = 0; row < mat.size(); row++) {
            if (mat[row][col] > 0) {
                return false;
            }
        }
        return true;
    }
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int R = mat.size(), C = mat[0].size();
        unordered_map<int, pair<int, int>> m;
        for (int row = 0; row < R; row++) {
            for (int col = 0; col < C; col++) {
                int value = mat[row][col];
                m[value] = {row, col};
            }
        }
        for (int index = 0; index < arr.size(); index++) {
            int val = arr[index];
            auto [row, col] = m[val];
            mat[row][col] = -mat[row][col]; // mark as seen
            if (checkRow(row, mat) || checkColumn(col, mat)) { // if completely seen
                return index;
            }
        }
        return -1;
    }
};
```

### Complexity Analysis

Let $m$ be the number of rows, and $n$ be the number of columns in the matrix.

- Time complexity: $O\left( m * n * (m + n) \right) \newline$
In the worst case, this approach iterates through approximately all $m * n$ elements. For each element, in the worst case we have to iterate over the row and column, which is of size $m + n$.

- Space complexity: $O\left( m * n \right) \newline$
The only additional space we are using is the map, which stores $m * n$ elements.


---


## Approach 2: Map with Optimized Checking

### Intuition

The previous approach has a time complexity of $O\left( m * n * (m + n) \right)$. To improve the time complexity, instead of iterating over the row and column each time, we maintain the count of how many elements we have seen in each row and column using two arrays.

### Algorithm

- Initialize `R` as the number of rows and `C` as the number of columms in `mat` and initialize a map `m`
- Initialize `rows` and `cols` as arrays to store how many seen elements are in each row and column
- For all rows `row` and all columns `col`, set the value `mat[row][col]`  to the position `[row, column]` in the map `m`
- For every index $i$:
    - Let `value` be the value of `arr[i]`
    - Get the row and column index, `row` and `col` from `m`, that is, `m[value]`
    - Mark the row and column as seen, that is, `rows[row] += 1` and `cols[col] += 1`
    - If the row or column is fully seen, that is, if `rows[row] == C` or `cols[col] == R`:
        - Return $i$

### Implementation

```python3 []
class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        R, C = len(mat), len(mat[0])
        rows = [0] * R
        cols = [0] * C
        m = {}
        for row in range(R):
            for col in range(C):
                value = mat[row][col]
                m[value] = [row, col]

        for index, val in enumerate(arr):
            row, col = m[val]
            rows[row] += 1 # mark row as seen
            cols[col] += 1 # mark col as seen
            if rows[row] == C or cols[col] == R: # if completely seen
                return index
        return -1
```
```C++ []
class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int R = mat.size(), C = mat[0].size();
        vector<int> rows(R), cols(C);
        unordered_map<int, pair<int, int>> m;
        for (int row = 0; row < R; row++) {
            for (int col = 0; col < C; col++) {
                int value = mat[row][col];
                m[value] = {row, col};
            }
        }
        for (int index = 0; index < arr.size(); index++) {
            int val = arr[index];
            auto [row, col] = m[val];
            rows[row]++; // mark row as seen
            cols[col]++; // mark col as seen
            if (rows[row] == C || cols[col] == R) { // if completely seen
                return index;
            }
        }
        return -1;
    }
};
```


### Complexity Analysis

Let $m$ be the number of rows, and $n$ be the number of columns in the matrix.

- Time complexity: $O\left( m * n \right) \newline$
In the worst case, this approach iterates through approximately all $m * n$ elements. For each element, we perform constant time operations.

- Space complexity: $O\left( m * n \right) \newline$
We are using a map which stores $m * n$ elements and two arrays of length $m$ and $n$. Therefore the space is dominated by $m * n$.


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