1632. Rank Transform of a Matrix

HardUnion FindGraphTopological SortArrayMatrixSorting
Leetcode Link

Problem Description

This problem asks us to rank elements in an m x n matrix according to certain rules. The rank of an element in the matrix is an integer starting from 1 and it indicates how large an element is in comparison to other elements. However, ranking is not done in isolation. It needs to consider the relations to other elements in the same row and column. The rules for determining the rank are as follows:

  • The ranks start at 1 and increase.
  • If two elements p and q are in the same row or column, the following conditions apply:
    • If p < q, then rank(p) must be less than rank(q).
    • If p == q, then rank(p) must be equal to rank(q).
    • If p > q, then rank(p) must be greater than rank(q).
  • The rank assigned should be as small as possible under the constraints.

The ultimate goal is to return a new matrix where for every element (row, col), the value is the rank of the original matrix[row][col].

Intuition

To solve this problem, we need a way to systematically go through the elements, determine their rank relative to their peers in the row and column and check the constraints that might affect their rank. The solution involves several steps:

  1. Sorting the Elements: We start by sorting all the elements in the matrix. Sorting ensures that we handle the smallest elements first, which allows us to assign the ranks progressively starting from the lowest rank.

  2. Union-Find Data Structure: We use a data structure called Union-Find (also known as Disjoint Set Union) to keep track of elements that are connected either through rows or columns and hence need to have some relation in terms of rank. Basically, this structure helps us to group elements that share the same row or column.

  3. Process Each Group of Equal Values: Since elements with the same value should have the same rank, we process the elements in groups where all elements have the same value. For each group, we find the maximum rank in the group based on the constraints and then assign the found rank to all the members of the group.

  4. Adjusting and Updating Ranks: After processing each group, we update the maximum rank found for each row and column to keep track of the latest ranks that have been assigned. This step is crucial because it ensures that for elements processed later, the rank is consistent with the earlier assigned ranks.

  5. Reset Union-Find for Each Group: Finally, after we have assigned ranks to a group of equal-valued elements, we need to reset the Union-Find structure for the next group. Doing this ensures that the new group is processed without any interference from the previous group's connections.

The provided solution code precisely implements this approach, systematically assigning ranks according to the problem's rules.

Learn more about Union Find, Graph, Topological Sort and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution is based on the intuition highlighted previously and can be detailed as follows:

  1. Store Elements by Value: We start by creating a dictionary (using defaultdict(list)), where we collect all the coordinates of the matrix elements keyed by their value. This will allow us to process all coordinates with the same value together.

  2. Initialization: A separate UnionFind class is defined with the find, union, and reset methods - this is essential for grouping elements by either row or column. Two additional lists, row_max and col_max, are initialized to keep track of the maximum rank in each row and column.

  3. Sorting and Processing: Each unique value in the matrix is sorted, and then, for each value, UnionFind is used to link all indices in the same row or column.

    • Link Elements: Through the union method, indices of the matrix that are in the same row or column are linked. Elements in the same row are directly unioned, while elements in the same column are offset by adding m to avoid conflict with row indices.

    • Determining Rank: For each group of equal elements (after union operations), the rank dictionary is used to determine the maximum rank of the connected elements by comparing it with the existing row_max and col_max.

  4. Assign Ranks: After computing the ranks, they are assigned to the answer matrix (ans) and the row_max and col_max are updated to reflect the new ranks for future elements to be processed.

  5. Reset for Next Value: Once all coordinates with the current value have been processed, the UnionFind structure is reset for each index that was involved in the current group. This prevents the previous connections from affecting the next set of unions.

The solution utilizes the UnionFind data structure to efficiently cluster elements that are affected by each other's rank due to their placement in the same rows or columns. The UnionFind's union method efficiently merges sets, and the find method ensures path compression for quick finds. Lastly, the reset method is used to disconnect the elements before moving on to the next value.

Here's a walkthrough of the code that corresponds to the solution steps:

  • The UnionFind class manages grouping and querying groups of cells based on row and column relations.
  • The matrixRankTransform function within the Solution class iterates through the matrix, groups the values, and processes them as per the rules.
  • The dictionary d is used to group all cell coordinates by their value to handle all cells with the same value simultaneously.
  • row_max and col_max arrays track the maximum rank for each row and column, respectively.
  • ans is the matrix that will store the final ranks for each cell.
  • The outermost loop for v in sorted(d): processes each group of cells with the same value.
  • Inside this loop, UnionFind operations are used alongside rank calculations (rank[uf.find(i)] = max(rank[uf.find(i)], row_max[i], col_max[j])), updating the ans, row_max, and col_max matrices.
  • The loop for i, j in d[v]: ensures each linked group is reset for the next value processing cycle.

By following this approach, the algorithm respects the ranking rules and efficiently computes the ranks for the entire matrix, producing a unique solution as required by the problem statement.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example Walkthrough

Let's take a small 2x3 matrix as an example to illustrate the solution approach.

1Matrix:
2[1, 2, 2]
3[3, 3, 1]

Step 1: Store Elements by Value

We create a dictionary that groups coordinates of matrix elements by their value:

  • Value 1: coordinate (0, 0) and (1, 2)
  • Value 2: coordinates (0, 1) and (0, 2)
  • Value 3: coordinates (1, 0) and (1, 1)

Step 2: Initialization

We define a UnionFind class with methods for union, find, and reset. Additionally, we initialize row_max and col_max lists to track the highest rank per row and column.

Step 3: Sorting and Processing

First, we sort the unique values in the matrix: [1, 2, 3].

Processing value 1:

  • Perform union operations for coords (0, 0) and (1, 2) (no actual union since they are not in the same row or column).
  • Set the rank for all the coords to 1, which is minimum, and update ans:
    • ans[0][0] = 1
    • ans[1][2] = 1
  • Update row_max and col_max accordingly to 1.

Processing value 2:

  • Perform union operations for coords (0, 1) and (0, 2) because they are in the same row.
  • Determine the rank as 2 since it should be higher than the rank of value 1 but as small as possible.
  • Update ans, row_max, and col_max:
    • ans[0][1] = 2, ans[0][2] = 2
    • row_max[0] = 2

Processing value 3:

  • Perform union operations for coords (1, 0) and (1, 1) because they are in the same row.
  • Determine the rank as 2 because it is the first occurrence in its row and column, but it must be greater than the rank of value 1.
  • Update ans, row_max, and col_max:
    • ans[1][0] = 2, ans[1][1] = 2
    • row_max[1] = 2, col_max[0] = 2, col_max[1] = 2

Step 4: Assign Ranks

The updated matrix ans after processing all values:

1[1, 2, 2]
2[2, 2, 1]

Step 5: Reset for Next Value

After each value is processed, we reset the UnionFind structure for the next group of elements.

By following these steps, we can see how the algorithm determines and assigns the ranks maintaining the rules given in the problem statement, leading to a consistent and correct ranking of the matrix elements. The UnionFind structure allowed us to efficiently group and rank cells that are related by their row and column positions.

Solution Implementation

1from collections import defaultdict
2
3# Define a Union-Find class to handle disjoint-set operations
4class UnionFind:
5    def __init__(self, n):
6        self.parents = list(range(n))  # Initial parent of each element is itself
7        self.sizes = [1] * n  # Size of each set starts as 1
8
9    # Find the representative (root) of the set that x belongs to
10    def find(self, x):
11        if self.parents[x] != x:
12            self.parents[x] = self.find(self.parents[x])  # Path compression
13        return self.parents[x]
14
15    # Union the sets containing elements a and b
16    def union(self, a, b):
17        root_a, root_b = self.find(a), self.find(b)
18        if root_a != root_b:  # If they are in different sets, merge them
19            # Always merge the smaller set into the larger one
20            if self.sizes[root_a] > self.sizes[root_b]:
21                self.parents[root_b] = root_a
22                self.sizes[root_a] += self.sizes[root_b]
23            else:
24                self.parents[root_a] = root_b
25                self.sizes[root_b] += self.sizes[root_a]
26
27    # Reset an element to be in its own set again
28    def reset(self, x):
29        self.parents[x] = x
30        self.sizes[x] = 1
31
32
33# Solution class to transform the ranks in a matrix
34class Solution:
35    def matrixRankTransform(self, matrix):
36        rows, cols = len(matrix), len(matrix[0])
37        value_to_coordinates = defaultdict(list)
38      
39        # Group all coordinates by their values in the matrix
40        for i, row in enumerate(matrix):
41            for j, value in enumerate(row):
42                value_to_coordinates[value].append((i, j))
43      
44        # Initialize the maximum rank seen so far for each row and column
45        row_max_rank = [0] * rows
46        col_max_rank = [0] * cols
47      
48        # Initialize the answer matrix with zeros
49        answer = [[0] * cols for _ in range(rows)]
50      
51        # UnionFind instance to keep track of connections
52        uf = UnionFind(rows + cols)
53      
54        # Process the values in increasing order
55        for value in sorted(value_to_coordinates):
56            rank = defaultdict(int)  # Dictionary to hold the potential rank of each root
57            # Union rows and columns that have the same value
58            for i, j in value_to_coordinates[value]:
59                uf.union(i, j + rows)
60            # Determine the rank for each group
61            for i, j in value_to_coordinates[value]:
62                root = uf.find(i)
63                rank[root] = max(rank[root], row_max_rank[i], col_max_rank[j])
64            # Assign the final rank to the matrix and update row and column maxima
65            for i, j in value_to_coordinates[value]:
66                root = uf.find(i)
67                current_rank = 1 + rank[root]
68                answer[i][j] = row_max_rank[i] = col_max_rank[j] = current_rank
69            # Reset the UnionFind after each value is processed
70            for i, j in value_to_coordinates[value]:
71                uf.reset(i)
72                uf.reset(j + rows)
73      
74        return answer
75
1import java.util.*;
2
3class UnionFind {
4    private int[] parent;  // Array to hold the representative (parent) for each element
5    private int[] size;    // Array to hold the size of each set
6
7    public UnionFind(int capacity) {
8        parent = new int[capacity];
9        size = new int[capacity];
10        for (int i = 0; i < capacity; ++i) {
11            parent[i] = i;  // Initially, each element is its own parent (self-loop)
12            size[i] = 1;    // And the size of each set is one
13        }
14    }
15
16    // Find the representative of the set that element x is part of
17    public int find(int x) {
18        if (parent[x] != x) {
19            parent[x] = find(parent[x]);  // Path compression heuristic
20        }
21        return parent[x];
22    }
23
24    // Unify the sets that elements `a` and `b` are part of
25    public void union(int a, int b) {
26        int rootA = find(a);
27        int rootB = find(b);
28        if (rootA != rootB) {
29            // Merge by size heuristic: smaller set points to the larger one
30            if (size[rootA] > size[rootB]) {
31                parent[rootB] = rootA;
32                size[rootA] += size[rootB];
33            } else {
34                parent[rootA] = rootB;
35                size[rootB] += size[rootA];
36            }
37        }
38    }
39
40    // Reset the representative and size for the element `x`
41    public void reset(int x) {
42        parent[x] = x;
43        size[x] = 1;
44    }
45}
46
47class Solution {
48    public int[][] matrixRankTransform(int[][] matrix) {
49        int height = matrix.length;       // Number of rows in matrix
50        int width = matrix[0].length;     // Number of columns in matrix
51      
52        // Mapping values to their indices in the matrix
53        TreeMap<Integer, List<int[]>> valueToIndices = new TreeMap<>();
54      
55        // Store the indices of each value in the matrix
56        for (int i = 0; i < height; ++i) {
57            for (int j = 0; j < width; ++j) {
58                valueToIndices.computeIfAbsent(matrix[i][j], k -> new ArrayList<>()).add(new int[] {i, j});
59            }
60        }
61      
62        // Arrays holding the max rank in each row and column
63        int[] rowMax = new int[height];
64        int[] colMax = new int[width];
65        // The matrix to hold the final rank transformation
66        int[][] rankTransform = new int[height][width];
67      
68        // Union-find structure for rows and columns
69        UnionFind unionFind = new UnionFind(height + width);
70        // Array holding the rank of each element in the union-find structure
71        int[] rank = new int[height + width];
72      
73        // Process the values in ascending order
74        for (var positions : valueToIndices.values()) {
75            // Union all positions with the same value
76            for (var position : positions) {
77                unionFind.union(position[0], position[1] + height);
78            }
79            // Compute the rank for each union-find root
80            for (var position : positions) {
81                int row = position[0], col = position[1];
82                rank[unionFind.find(row)] = Math.max(rank[unionFind.find(row)], Math.max(rowMax[row], colMax[col]));
83            }
84            // Assign the rank to the positions and update the max row and column ranks
85            for (var position : positions) {
86                int row = position[0], col = position[1];
87                rankTransform[row][col] = 1 + rank[unionFind.find(row)];
88                rowMax[row] = rankTransform[row][col];
89                colMax[col] = rankTransform[row][col];
90            }
91            // Reset the union-find structure for the next value
92            for (var position : positions) {
93                unionFind.reset(position[0]);
94                unionFind.reset(position[1] + height);
95            }
96        }
97        return rankTransform;
98    }
99}
100
1#include <vector>
2#include <map>
3#include <numeric>
4using namespace std;
5
6// Union-Find class to manage disjoint sets operations.
7class UnionFind {
8public:
9    // Constructor initializes the union-find structure.
10    UnionFind(int n) {
11        parents.resize(n);
12        sizes.resize(n, 1);
13        iota(parents.begin(), parents.end(), 0);  // Set each element to be its own parent.
14    }
15
16    // Unite two subsets into a single subset if they are different.
17    void unite(int a, int b) {
18        int rootA = find(a), rootB = find(b);
19        if (rootA != rootB) {
20            // Join the two trees by size. Attach the smaller tree to the larger one.
21            if (sizes[rootA] > sizes[rootB]) {
22                parents[rootB] = rootA;
23                sizes[rootA] += sizes[rootB];
24            } else {
25                parents[rootA] = rootB;
26                sizes[rootB] += sizes[rootA];
27            }
28        }
29    }
30
31    // Find the root parent of a node. Path compression is applied.
32    int find(int x) {
33        if (parents[x] != x) {
34            parents[x] = find(parents[x]);  // Path compression for efficiency.
35        }
36        return parents[x];
37    }
38
39    // Resets a node to be a standalone subset.
40    void reset(int x) {
41        parents[x] = x;
42        sizes[x] = 1;
43    }
44
45private:
46    vector<int> parents; // Contains parent/representative for each node.
47    vector<int> sizes;   // Size of each set (used to keep trees balanced).
48};
49
50class Solution {
51public:
52    // Transform the given matrix so that each element is the smallest rank greater than all elements with a smaller value in its row and column.
53    vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {
54        int m = matrix.size(), n = matrix[0].size();
55        map<int, vector<pair<int, int>>> valueToCoordinates;
56
57        // Group cells by their values in the matrix.
58        for (int i = 0; i < m; ++i) {
59            for (int j = 0; j < n; ++j) {
60                valueToCoordinates[matrix[i][j]].emplace_back(i, j);
61            }
62        }
63
64        vector<int> rowMax(m, 0); // Max rank of each row.
65        vector<int> colMax(n, 0); // Max rank of each column.
66        vector<vector<int>> answer(m, vector<int>(n, 0)); // Store ranks for answer.
67        UnionFind unionFind(m + n); // Union-find instance for rows and columns.
68        vector<int> rank(m + n, 0); // Rank of each combined set of row and column.
69
70        // Iterate over groups of cells by ascending values.
71        for (auto& [value, cells] : valueToCoordinates) {
72            // Unite rows and columns of cells with same value.
73            for (auto& [row, col] : cells) {
74                unionFind.unite(row, col + m);
75            }
76
77            // Compute the maximum rank for each set.
78            for (auto& [row, col] : cells) {
79                int root = unionFind.find(row);
80                rank[root] = max({rank[root], rowMax[row], colMax[col]});
81            }
82
83            // Update the ranks in the answer matrix and update row/column max ranks.
84            for (auto& [row, col] : cells) {
85                answer[row][col] = rowMax[row] = colMax[col] = rank[unionFind.find(row)] + 1;
86            }
87
88            // Reset the union-find structure for the next value.
89            for (auto& [row, col] : cells) {
90                unionFind.reset(row);
91                unionFind.reset(col + m);
92            }
93        }
94
95        return answer; // Return the rank-transformed matrix.
96    }
97};
98
1// Represents each node's parent and size for Union-Find operations
2let parents: number[];
3let sizes: number[];
4
5// Initializes the Union-Find structure with `n` elements.
6function initializeUnionFind(n: number): void {
7    parents = Array.from({length: n}, (_, index) => index); 
8    sizes = new Array(n).fill(1);
9}
10
11// Finds the root of the set that element `x` belongs to.
12function find(x: number): number {
13    if (parents[x] !== x) {
14        parents[x] = find(parents[x]); // Path compression
15    }
16    return parents[x];
17}
18
19// Unites the sets to which elements `a` and `b` belong.
20function unite(a: number, b: number): void {
21    const rootA = find(a);
22    const rootB = find(b);
23    if (rootA !== rootB) {
24        // Attach the smaller tree to the larger one.
25        if (sizes[rootA] > sizes[rootB]) {
26            parents[rootB] = rootA;
27            sizes[rootA] += sizes[rootB];
28        } else {
29            parents[rootA] = rootB;
30            sizes[rootB] += sizes[rootA];
31        }
32    }
33}
34
35// Resets the subset that includes `x` to be standalone.
36function reset(x: number): void {
37    parents[x] = x;
38    sizes[x] = 1;
39}
40
41// Transforms the input `matrix` based on the problem statement.
42function matrixRankTransform(matrix: number[][]): number[][] {
43    const m = matrix.length;
44    const n = matrix[0].length;
45    const valueToCoordinates: Map<number, Array<[number, number]>> = new Map();
46
47    // Group cells by their values
48    for (let i = 0; i < m; ++i) {
49        for (let j = 0; j < n; ++j) {
50            if (!valueToCoordinates.has(matrix[i][j])) {
51                valueToCoordinates.set(matrix[i][j], []);
52            }
53            valueToCoordinates.get(matrix[i][j])!.push([i, j]);
54        }
55    }
56
57    const rowMax = new Array(m).fill(0); // Max rank of each row
58    const colMax = new Array(n).fill(0); // Max rank of each column
59    const answer = Array.from({length: m}, () => new Array(n).fill(0)); // Initialized rank matrix
60
61    // Process coordinates grouped by value
62    for (const [value, cells] of valueToCoordinates) {
63        initializeUnionFind(m + n); // Union-find for rows and columns
64        const rank = new Array(m + n).fill(0); // Rank for each set
65
66        // Union rows and columns
67        for (const [row, col] of cells) {
68            unite(row, col + m);
69        }
70
71        // Find the max rank for the current set of cells
72        for (const [row, col] of cells) {
73            const root = find(row);
74            rank[root] = Math.max(rank[root], rowMax[row], colMax[col]);
75        }
76
77        // Assign ranks to the answer matrix, update rowMax and colMax
78        for (const [row, col] of cells) {
79            const rootRank = rank[find(row)] + 1;
80            answer[row][col] = rootRank;
81            rowMax[row] = colMax[col] = rootRank;
82        }
83      
84        // No need to reset Union-Find because it's reinitialized at the beginning of each value group
85    }
86
87    return answer; // Return the rank-transformed matrix
88}
89
Not Sure What to Study? Take the 2-min Quiz๏ผš

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

The given code snippet is for the rank transformation of a matrix using the union-find data structure. We can analyze its time and space complexity in the following way:

Time Complexity:

  1. Initialization: Initialization of union-find has a time complexity of O(m + n) because it initializes an array with m + n elements.
  2. Building the dictionary d: To build the dictionary, we go through each cell of the matrix; hence, it has a time complexity of O(m * n).
  3. Sorting the dictionary keys: Sorting the values present in the matrix which will be O(k log k) where k is the number of distinct values in the matrix. Normally, k can be bound by m * n.
  4. Union Operations: For each value, we potentially perform a union for each element in d[v] which is the number of times that value occurs. If we assume that the amortized time complexity for each union operation is O(alpha(m + n)), where alpha is the inverse Ackermann function (which is very slowly growing and can be considered nearly constant), then in the worst case it is O(m * n * alpha(m + n)).
  5. Path Compression: Path compression is done during the find operations which is included in the amortized time for union operations.
  6. Rank Calculation and Answer Update: Since we iterate through all values in d[v] again to calculate rank and to update ans, row_max, and col_max, we do a total of O(m * n) work here.
  7. Reset at the end: We reset the union-find for each coordinate visited by d[v], taking O(m + n) time in total.

The overall time complexity is therefore dominated by the sorting and the union-find operations and can be given as O((m * n) * alpha(m + n) + k log k).

However, since k <= m * n, the complexity can be viewed as O((m * n) * (log(m * n) + alpha(m + n))).

Space Complexity:

  1. UnionFind Data Structure: The space complexity of union-find is O(m + n) because it maintains two arrays of size m + n.
  2. Dictionary d: The space complexity for d is O(m * n) since in the worst case it could contain all the cells of the matrix if each cell has a distinct value.
  3. Auxiliary data structures: row_max and col_max each have a space complexity of O(m) and O(n) respectively, and ans has a space complexity of O(m * n).
  4. Rank dictionary: This has a space complexity that can go up to O(m + n) in the worst case.

The overall space complexity combines the UnionFind structure, the dictionary d, row_max, col_max, ans, and rank dictionary, but is still principally determined by the number of elements in the matrix.

So the overall space complexity is O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ