# [LeetCode 1632. Rank Transform of a Matrix](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/614/week-2-august-8th-august-14th/3874/)
### Daily challenge Aug 8, 2021 (HARD)

>Given an `m x n matrix`, return a new matrix `answer` where `answer[row][col]` is the **rank** of `matrix[row][col]`.
>
>The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:
>
>* The rank is an integer starting from 1.
>* If two elements `p` and `q` are in the **same row or column**, then:
>* * If **`p < q`** then **`rank(p) < rank(q)`**
>* * If **`p == q`** then **`rank(p) == rank(q)`**
>* * If **`p > q`** then **`rank(p) > rank(q)`**
>* The rank should be **as small as possible**.
>
>It is guaranteed that answer is unique under the given rules.


:::info
**Example 1:**
**Input:** matrix = [[1,2],[3,4]]
**Output:** [[1,2],[2,3]]
**Explanation:**
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] > matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] > matrix[0][1], matrix[1][1] > matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
:::


:::info
**Example 2:**
**Input:** matrix = [[7,7],[7,7]]
**Output:** [[1,1],[1,1]]
:::


:::info
**Example 3:**
**Input:** matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
**Output:** [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]
:::


:::info
**Example 4:**
**Input:** matrix = [[7,3,6],[1,4,5],[9,8,2]]
**Output:** [[5,1,4],[1,2,3],[6,3,1]]
:::

:::warning
**Constraints:**
* m == matrix.length
* n == matrix[i].length
* 1 <= m, n <= 500
* -109 <= matrix[row][col] <= 109
:::

---

### Approach 1 : Union Find
**`216 ms ( 83.58% )`** **`O( NNlog(MN) )`**

:::success
* 將元素的位置轉換成一維記錄到 **`map`** ---> **`index = i * n + j`**。
> m = 3, n = 3。
> row = 1, col = 1 ---> **`index = 1 * 3 + 1 = 4`**。
* **`root, rank`** 大小為 `m + n`
---> **`0 ~ m - 1 = row`**。
---> **`m ~ m + n - 1 = col`**。
:::

:::success
**Union Find** :
假設 `A 跟 B 一組`，給他們編號 `B`，後來又有 `B 跟 C 一組`，這時給他們編號 `C`，但是 `A` 也是跟 `B、C` 一組的，所以 `A` 同時也需要一起更新。

下面的方法會將 `row、col` 各做一次尋找。
:::

* **`map<int, vector<int>> list`** 紀錄所有元素的位置。
**`vector<int> rank(m + n, 0)`** 紀錄當前 `row、col` 的 `rank` 最大值。
**`vector<int> root(m + n, 0)`** 用於紀錄 `Union Find` 的組別。

1. 先將所有元素存入 `list`。
2. 因為 `list` 已經是排序過的，所以從頭開始遍歷，可以確保當前元素是最大值，接著判斷該元素下的所有 `index`。
> * 先將 `root` 初始化。
> * 接著使用 `Union Find` 將大小相同的元素分組，同時更新 `rank` 的最大值，判斷哪些 `col 或 row 相同`，他們的 `rank` 必須相同。
> * 透過剛剛的分組，賦予每個組別 `rank`。
> ---> **`rank2`** 紀錄下一輪的值，可以避免相同組別被賦予到不同的值，最後再丟回 **`rank`**。
>```cpp=38
> rank2[i] = rank[group] + 1;
> rank2[j + m] = rank[group] + 1;
>```

> 以 `2` 為例的 `Union Find`。
> 給 `rank` 值 ---> 找 `group`。
>

class Solution {
public:
    vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        map<int, vector<int>> list;    // val, index
        
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                list[matrix[i][j]].push_back(i * n + j);
            }
        }
        
        vector<int> rank(m + n, 0);
        vector<vector<int>> ans(m, vector<int>(n));
        
        for (auto & it : list) {
            vector<int> root(m + n, 0); // for Union find ( 0~n-1 = row / n ~ n+m-1 = col )
            for(int i=0; i<m+n; i++){
                root[i] = i;
            }

            // use Union find to find group
            for (auto & a: it.second) {
                int i = a / n, j = a % n;
                int r1 = find(root, i), r2 = find(root, j + m);
                
                root[r1] = r2;  // make row point to column
                rank[r2] = max(rank[r1], rank[r2]);
            }

            // set rank
            auto rank2 = rank;
            for (auto & a : it.second) {
                int i = a / n, j = a % n;
                int group = find(root, i);
                
                ans[i][j] = rank[group] + 1;
                rank2[i] = rank[group] + 1;
                rank2[j + m] = rank[group] + 1;
            }
            
            rank = rank2;
        }
        
        return ans;
    }
    
    // Union find
    int find(vector<int>& root, int x) {
        if (root[x] != x) root[x] = find(root, root[x]);    // update root[x]
        return root[x];
    }
};