<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 Solution:

    def process_rank(self, same_elements, answer_ranks):
        
        def find_parent_idx(element_idx, parent_arr):
            if parent_arr[element_idx] < 0:
                return element_idx
            parent_arr[element_idx] = find_parent_idx(parent_arr[element_idx], parent_arr)
            return parent_arr[element_idx]

        # either we can create 2 arrays for row parent and col parent but now instead of creating 2 seperate arrays for row 
        # parent and col parent we will use same array by partitioning it into 2 parts 0 to n-1 for rows and n to n+m-1 for columns
        parent_arr = [-1] * (self.rows + self.cols)
        # here in this array we store parent of each element and the index that do not have parent i.e. value < 0, it will store the 
        # max_rank for the index to be allocated but in -ve so that we can use the conditon if parent_arr[idx] < 0, means it is final 
        # parent of group and it holds the rank of this group
        for item in same_elements:
            item_row, item_col = item[1], item[2]
            row_parent_idx, col_parent_idx = find_parent_idx(item_row, parent_arr), find_parent_idx(self.rows + item_col, parent_arr)

            if row_parent_idx != col_parent_idx:  # if this pair row and column are not merged yet then
                # max_rank among same elements i.e. elements with same value
                max_rank = -min(parent_arr[row_parent_idx], parent_arr[col_parent_idx]) # here -ve of min bcz max is stored as -ve value so first take min then -(-ve) = +ve
                # here we compare this max_rank of same element with rank of all other elements in this row and column
                max_rank = max(max_rank, max(self.rows_max[item_row], self.cols_max[item_col]) + 1)  # here it is important to do max(row, col) + 1, bcz row_max holds max till now same for column
                # now we have max rank for this row and column so we set the value in parent array for this group
                parent_arr[row_parent_idx] = -max_rank  # assign rank as -ve value to maintain parent property parent_arr[idx] < 0 means it's the final leader of group
                parent_arr[col_parent_idx] = row_parent_idx
        
        # here we are going to update the result array
        for item in same_elements:
            item_row, item_col = item[1], item[2]
            row_parent_idx = find_parent_idx(item_row, parent_arr)
            rank = -parent_arr[row_parent_idx]

            answer_ranks[item_row][item_col] = rank
            self.rows_max[item_row] = rank
            self.cols_max[item_col] = rank

    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]:
        # here the catch is that elements can be equal and all equal elements from same row will have same rank
        # and all equal elements in same column will have same rank, so let's say in ith row elements 
        # at i,j and i,j+x and i,j+y are same, so all of them will have same rank, now assume elements 
        # at a,j or b,j+x or c,j+y also have same elements, so they will also have same rank and last case is elements
        # at a,p or b,q or c,r can also be same, so they will also have same rank, hence we need to keep all of these 
        # in same group, and for grouping we use union find, there can be other places where same element may exist 
        # but groups will be formed basis on same row and column.
        # now we will process elements in increasing order and for an element we would have processes all smaller 
        # elements, so we can easily find max rank assigned in a row till now and max rank assigned in a column till now,
        # or instead of finding it each time we can store in rowmax and colmax array and we can update this array each time we process
        #  a larger element
        self.rows, self.cols = len(matrix), len(matrix[0])
        self.rows_max, self.cols_max = [0] * self.rows, [0] * self.cols  # rows[i] stores max rank till now in ith row, cols[j] stores max rank till now in jth col
        # hence we need to store all elements in a array and sort that array
        all_elements = []
        for r in range(self.rows):
            for c in range(self.cols):
                all_elements.append((matrix[r][c], r, c))  # when processing element we also need the original position where this particular
                #  element belongs, bcz after sorting original order will change
        all_elements.sort(key=lambda item: item[0])
        # now elements are sorted so let's process each element, but if elements are same we will process all of them together bcz they belong to same group
        answer_ranks = [[0]*self.cols for r in range(self.rows)]
        same_elements = []
        # we can easily calculate rank but the problem is when 2d array contains same elements in same row or same column, so that's why we need union find to process all those elements together based on their group
        for item in all_elements:
            if not same_elements or item[0] == same_elements[-1][0]:
                same_elements.append(item)
            else:
                self.process_rank(same_elements, answer_ranks)
                same_elements = [item]
        # in above last element will not be processed so we will process it here
        self.process_rank(same_elements, answer_ranks)
        return answer_ranks

57000