<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, n):
        self.parents = list(range(n))  # Initial parent of each element is itself
        self.sizes = [1] * n  # Size of each set starts as 1

    # Find the representative (root) of the set that x belongs to
    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])  # Path compression
        return self.parents[x]

    # Union the sets containing elements a and b
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a != root_b:  # If they are in different sets, merge them
            # Always merge the smaller set into the larger one
            if self.sizes[root_a] > self.sizes[root_b]:
                self.parents[root_b] = root_a
                self.sizes[root_a] += self.sizes[root_b]
            else:
                self.parents[root_a] = root_b
                self.sizes[root_b] += self.sizes[root_a]

    # Reset an element to be in its own set again
    def reset(self, x):
        self.parents[x] = x
        self.sizes[x] = 1


# Solution class to transform the ranks in a matrix
class Solution:
    def matrixRankTransform(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        value_to_coordinates = defaultdict(list)
      
        # Group all coordinates by their values in the matrix
        for i, row in enumerate(matrix):
            for j, value in enumerate(row):
                value_to_coordinates[value].append((i, j))
      
        # Initialize the maximum rank seen so far for each row and column
        row_max_rank = [0] * rows
        col_max_rank = [0] * cols
      
        # Initialize the answer matrix with zeros
        answer = [[0] * cols for _ in range(rows)]
      
        # UnionFind instance to keep track of connections
        uf = UnionFind(rows + cols)
      
        # Process the values in increasing order
        for value in sorted(value_to_coordinates):
            rank = defaultdict(int)  # Dictionary to hold the potential rank of each root
            # Union rows and columns that have the same value
            for i, j in value_to_coordinates[value]:
                uf.union(i, j + rows)
            # Determine the rank for each group
            for i, j in value_to_coordinates[value]:
                root = uf.find(i)
                rank[root] = max(rank[root], row_max_rank[i], col_max_rank[j])
            # Assign the final rank to the matrix and update row and column maxima
            for i, j in value_to_coordinates[value]:
                root = uf.find(i)
                current_rank = 1 + rank[root]
                answer[i][j] = row_max_rank[i] = col_max_rank[j] = current_rank
            # Reset the UnionFind after each value is processed
            for i, j in value_to_coordinates[value]:
                uf.reset(i)
                uf.reset(j + rows)
      
        return answer

54800