Ninja’s Transformation

Hard
0/120
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
Walmart

Problem statement

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

Example

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.
Detailed explanation ( Input/output format, Notes, Images )
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

Sample input 1:

2
2 2
1 2
3 4
2 2
7 7
7 7

Sample output 1:

1 2
2 3
1 1
1 1

Explanation of sample input 1:

Test Case 1:
For this test case, we calculate the rank of the matrix in this way:

Example

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.

Test Case 2:

Example

For this test case as all elements are equals so the rank of each index is ‘1’.

Sample input 2:

2
4 3
20 -21 14
-19 4 19
22 -47 24
-19 4 19
3 3
7 3 6
1 4 5
9 8 2

Sample output 2:

4 2 3
1 3 4
5 1 6
1 3 4
5 1 4
1 2 3
6 3 1
Hint

Can you think of a union-find?

Approaches (2)
Union find and sorting

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.
Time Complexity

O((N * M) * log(N * M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.

 

We are sorting our matrix and then comparing it for calculating the rank that takes O((N * M) * log(N * M) time. Hence the overall time complexity is O((N * M) * log(N * M). 

Space Complexity

O(N),  where ‘N’ is the number of rows in the matrix.

 

As we are using a set for storing them in pairs that takes O(N) space. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja’s Transformation
Full screen
Console