Last Updated: 4 Apr, 2021
Ninja’s Transformation
Hard
Asked in company
Nowadays everybody is working on transforming his body in gyms so our ninja is also interested in transformation. But as our ninja is interested in coding more than the body so he thinks of transforming the rank of the matrix. So he can do transformation as well as coding.
You will be given a matrix ‘mat’ of size ‘M * N’. Your task is to return a new matrix ‘ANSWER’ where ‘ANSWER[row][col]’ is the rank of ‘MATRIX[row][col]’.
For calculating the rank of the matrix following rule must be followed:
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.
Example:
Suppose the matrix is [ [ 1, 2 ], [ 3, 4 ] ] so we return rank as [ [ 1, 2 ], [ 2, 3 ] ] as
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.
Input format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow:
Each test case’s first line contains two space-separated integers, ‘N’ and ‘M’, denoting the number of rows and columns in the matrix.
The next ‘N’ lines contain ‘M’ integers that denoting the elements of the MATRIX.
Output format:
For every test case, print 'N' lines each line containing 'M' space-seprated integers denoting the elements of the new matrix containing the rank of the matrix.
The output of each test case will be printed a separate line.
Note:
You are not required to print anything explicitly. It has already been taken care of just implement the function.
Constraints:
1 <= T <= 10
1 <= N, M <= 100
-10 ^ 5 <= MATRIX[i][j] <= 10^5
Where ‘T’ is the number of test cases, ‘N’ is the number of rows, and ‘M' is the number of columns in a 'MATRIX'.
Time limit: 1 second
Approaches
The idea here is to process values from the smallest to largest, and track the current rank for each row of rows[i] and column col[j]. Because our values are sorted, ranks will always increase for the next value. For each group, we need to identify a rank, which is a maximum rank (plus one) of all included rows and columns.
- First, we collect all values (and their coordinates) and sort them.
- Then, we process all cells with the same value. We arrange cells into groups using Union-Find, so we can determine the rank for each group.
- We allocate rows + columns size for the disjoint set and join rows and columns. In the disjoint set, an element points to its parent, and the root parent points to itself. we use a negative value to indicate a parent, so we can use it to track the rank of the group. In our case, the rank is the maximum rank of all rows and columns in the group (plus one) - and this is the value we will assign to all cells in the group.
- Finally, we update the rank for affected rows and columns and return the new matrix.
The idea here is to use the same idea above but instead of sorting, we use a map for storing them from smallest to the largest.
- Firstly we try to find out all the cells with the same rank i.e cells with the same values in a row or column.
- Assign ranks first to cells with smaller value then to cells with a larger value.
- Maintain the largest rank so far in each row and column.
- Value of a cell (i,j) is matrix[i][j]
- Assigning ranks: [ start with a set of cells which will get the same rank and have the lowest value ]
- Traverse all cells which will get the same rank.
- Let x be the max rank till now in all the rows and columns visited while traversing.
- Assign current cells with x + 1
- Repeat the above step for other sets of cells that will get the same rank and have a greater or equal value to the previously assigned set of cells.
- Now we returned the transformed matrix