{"id":7570,"date":"2020-10-28T20:38:19","date_gmt":"2020-10-29T03:38:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7570"},"modified":"2020-10-28T20:43:37","modified_gmt":"2020-10-29T03:43:37","slug":"leetcode-1632-rank-transform-of-a-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1632-rank-transform-of-a-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1632. Rank Transform of a Matrix"},"content":{"rendered":"\n<p>Given an&nbsp;<code>m x n<\/code>&nbsp;<code>matrix<\/code>, return&nbsp;<em>a new matrix&nbsp;<\/em><code>answer<\/code><em>&nbsp;where&nbsp;<\/em><code>answer[row][col]<\/code><em>&nbsp;is the&nbsp;<\/em><em><strong>rank<\/strong>&nbsp;of&nbsp;<\/em><code>matrix[row][col]<\/code>.<\/p>\n\n\n\n<p>The&nbsp;<strong>rank<\/strong>&nbsp;is an&nbsp;<strong>integer<\/strong>&nbsp;that represents how large an element is compared to other elements. It is calculated using the following rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The rank is an integer starting from&nbsp;<code>1<\/code>.<\/li><li>If two elements&nbsp;<code>p<\/code>&nbsp;and&nbsp;<code>q<\/code>&nbsp;are in the&nbsp;<strong>same row or column<\/strong>, then:<ul><li>If&nbsp;<code>p &lt; q<\/code>&nbsp;then&nbsp;<code>rank(p) &lt; rank(q)<\/code><\/li><li>If&nbsp;<code>p == q<\/code>&nbsp;then&nbsp;<code>rank(p) == rank(q)<\/code><\/li><li>If&nbsp;<code>p &gt; q<\/code>&nbsp;then&nbsp;<code>rank(p) &gt; rank(q)<\/code><\/li><\/ul><\/li><li>The&nbsp;<strong>rank<\/strong>&nbsp;should be as&nbsp;<strong>small<\/strong>&nbsp;as possible.<\/li><\/ul>\n\n\n\n<p>It is guaranteed that&nbsp;<code>answer<\/code>&nbsp;is unique under the given rules.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/18\/rank1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> matrix = [[1,2],[3,4]]\n<strong>Output:<\/strong> [[1,2],[2,3]]\n<strong>Explanation:<\/strong>\nThe rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.\nThe rank of matrix[0][1] is 2 because matrix[0][1] &gt; matrix[0][0] and matrix[0][0] is rank 1.\nThe rank of matrix[1][0] is 2 because matrix[1][0] &gt; matrix[0][0] and matrix[0][0] is rank 1.\nThe 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.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/18\/rank2.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> matrix = [[7,7],[7,7]]\n<strong>Output:<\/strong> [[1,1],[1,1]]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/18\/rank3.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]\n<strong>Output:<\/strong> [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/10\/18\/rank4.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> matrix = [[7,3,6],[1,4,5],[9,8,2]]\n<strong>Output:<\/strong> [[5,1,4],[1,2,3],[6,3,1]]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><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>&nbsp;&lt;= matrix[row][col] &lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Union Find<\/strong><\/h2>\n\n\n\n<p>Group cells by their values, process groups (cells that have the same value) in ascending order (smaller number has smaller rank).<\/p>\n\n\n\n<p>For cells that are in the same row and same cols union them using union find, they should have the same rank which equals to max(max_rank_x[cols], max_rank_y[rows]) + 1.<\/p>\n\n\n\n<p>Time complexity: O(m*n*(m+n))<br>Space complexity: O(m*n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass DSU {\npublic:\n  DSU(int n): p_(n, -1) {}\n  int find(int x) {\n    return p_[x] == -1 ? x : p_[x] = find(p_[x]);\n  }  \n  void merge(int x, int y) {\n    x = find(x), y = find(y);\n    if (x != y) p_[x] = y;    \n  }\nprivate:\n  vector<int> p_;\n};\n\nclass Solution {\npublic:\n  vector<vector<int>> matrixRankTransform(vector<vector<int>>& matrix) {\n    const int m = matrix.size();\n    const int n = matrix[0].size();\n    vector<vector<int>> ans(m, vector<int>(n));\n    map<int, vector<pair<int, int>>> mp; \/\/ val -> {positions}\n    for (int y = 0; y < m; ++y)\n      for (int x = 0; x < n; ++x)\n        mp[matrix[y][x]].emplace_back(x, y);\n    vector<int> rx(n), ry(m);\n    for (const auto& [val, ps]: mp) {\n      DSU dsu(n + m);\n      vector<vector<pair<int, int>>> cc(n + m); \/\/ val -> {positions}\n      for (const auto& [x, y]: ps)\n        dsu.merge(x, y + n);\n      for (const auto& [x, y]: ps)        \n        cc[dsu.find(x)].emplace_back(x, y);      \n      for (const auto& ps: cc) {\n        int rank = 1;\n        for (const auto& [x, y]: ps)\n          rank = max(rank, max(rx[x], ry[y]) + 1);\n        for (const auto& [x, y]: ps)\n          rx[x] = ry[y] = ans[y][x] = rank;   \n      }      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an&nbsp;m x n&nbsp;matrix, return&nbsp;a new matrix&nbsp;answer&nbsp;where&nbsp;answer[row][col]&nbsp;is the&nbsp;rank&nbsp;of&nbsp;matrix[row][col]. The&nbsp;rank&nbsp;is an&nbsp;integer&nbsp;that represents how large an element is compared to other elements. It is calculated using the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[665,77,217,216,113],"class_list":["post-7570","post","type-post","status-publish","format-standard","hentry","category-graph","tag-cc","tag-graph","tag-hard","tag-matrix","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7570","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7570"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7570\/revisions"}],"predecessor-version":[{"id":7572,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7570\/revisions\/7572"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}