<p>Given an <code>m x n</code> <code>matrix</code>, return <em>a new matrix </em><code>answer</code><em> where </em><code>answer[row][col]</code><em> is the </em><em><strong>rank</strong> of </em><code>matrix[row][col]</code>.</p>

<p>The <strong>rank</strong> is an <strong>integer</strong> that represents how large an element is compared to other elements. It is calculated using the following rules:</p>

<ul>
	<li>The rank is an integer starting from <code>1</code>.</li>
	<li>If two elements <code>p</code> and <code>q</code> are in the <strong>same row or column</strong>, then:
	<ul>
		<li>If <code>p &lt; q</code> then <code>rank(p) &lt; rank(q)</code></li>
		<li>If <code>p == q</code> then <code>rank(p) == rank(q)</code></li>
		<li>If <code>p &gt; q</code> then <code>rank(p) &gt; rank(q)</code></li>
	</ul>
	</li>
	<li>The <strong>rank</strong> should be as <strong>small</strong> as possible.</li>
</ul>

<p>The test cases are generated so that <code>answer</code> is unique under the given rules.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/18/rank1.jpg" style="width: 442px; height: 162px;" />
<pre>
<strong>Input:</strong> matrix = [[1,2],[3,4]]
<strong>Output:</strong> [[1,2],[2,3]]
<strong>Explanation:</strong>
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] &gt; matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] &gt; matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] &gt; matrix[0][1], matrix[1][1] &gt; matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/18/rank2.jpg" style="width: 442px; height: 162px;" />
<pre>
<strong>Input:</strong> matrix = [[7,7],[7,7]]
<strong>Output:</strong> [[1,1],[1,1]]
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/18/rank3.jpg" style="width: 601px; height: 322px;" />
<pre>
<strong>Input:</strong> matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
<strong>Output:</strong> [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>-10<sup>9</sup> &lt;= matrix[row][col] &lt;= 10<sup>9</sup></code></li>
</ul>

class UnionFind:
    def __init__(self, nodes):
        # Initialize parent and rank dictionaries
        self.parent = {node: node for node in nodes}
        self.rank = {node: 0 for node in nodes}

        rowwise_mapping = {}
        columnwise_mapping = {}

        for node in nodes:
            i, j = node
            if i in rowwise_mapping:
                self.union(rowwise_mapping[i], node)
            else:
                rowwise_mapping[i] = node
            
            if j in columnwise_mapping:
                self.union(columnwise_mapping[j], node)
            else:
                columnwise_mapping[j] = node

    def find(self, node):
        # Path compression
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)

        if root1 != root2:
            # Union by rank
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

    def get_groups(self):
        # Create a dictionary to store groups
        groups = {}
        for node in self.parent:
            root = self.find(node)
            if root not in groups:
                groups[root] = []
            groups[root].append(node)
        
        # Convert dictionary values to a list of groups
        return list(groups.values())


class Solution:
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix)
        n = len(matrix[0])

        elements = defaultdict(list)

        for i in range(m):
            for j in range(n):
                elements[matrix[i][j]].append((i, j))
                # elements.append((matrix[i][j], i, j))

        rowRank = [0 for i in range(m)]
        columnRank = [0 for i in range(n)]

        for num in sorted(elements):
            # print("num: {}, nodes: {}".format(num, elements[num]))
            same_elements = elements[num]
            if len(same_elements) == 1:
                i, j = same_elements[0]
                matrix[i][j] = max(rowRank[i], columnRank[j]) + 1
                rowRank[i] = matrix[i][j]
                columnRank[j] = matrix[i][j]
            else:
                uf = UnionFind(same_elements)
                groups = uf.get_groups()
                for group in groups:
                    # calculate the rank for this group
                    rank = 0
                    for i, j in group:
                        if rank < max(rowRank[i], columnRank[j]) + 1:
                            rank = max(rowRank[i], columnRank[j]) + 1
                    #updaate the rank for this group
                    for i, j in group:
                        rowRank[i] = rank
                        columnRank[j] = rank
                        matrix[i][j] = rank    


        # while len(elements) > 0:
        #     if len(elements) >= 2 and elements[0][0] == elements[1][0]:
        #         value = elements[0][0]
        #         # merge
        #         same_elements = []
        #         while len(elements) and elements[0][0] == value:
        #             same_elements.append(elements.pop(0))

        #         uf = UnionFind(same_elements)
        #         groups = uf.get_groups()
        #         # print(groups)
        #         for group in groups:
        #             # calculate the rank for this group
        #             rank = 0
        #             for element in group:
        #                 _, i, j = element
                        
        #                 if rank < max(rowRank[i], columnRank[j]) + 1:
        #                     rank = max(rowRank[i], columnRank[j]) + 1
        #             # updaate the rank for this group
        #             for element in group:
        #                 _, i, j = element
        #                 rowRank[i] = rank
        #                 columnRank[j] = rank
        #                 matrix[i][j] = rank

        #     else:
        #         element = elements.pop(0)
        #         _, i, j = element
        #         matrix[i][j] = max(rowRank[i], columnRank[j]) + 1
        #         rowRank[i] = matrix[i][j]
        #         columnRank[j] = matrix[i][j]


        return matrix

82900