{"id":6909,"date":"2020-06-13T20:41:08","date_gmt":"2020-06-14T03:41:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6909"},"modified":"2020-06-13T20:42:56","modified_gmt":"2020-06-14T03:42:56","slug":"leetcode-1476-subrectangle-queries","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-1476-subrectangle-queries\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1476. Subrectangle Queries"},"content":{"rendered":"\n<p>Implement the class&nbsp;<code>SubrectangleQueries<\/code>&nbsp;which receives a&nbsp;<code>rows x cols<\/code>&nbsp;rectangle as a matrix of integers in the constructor and supports two methods:<\/p>\n\n\n\n<p>1.<code>&nbsp;updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Updates all values with&nbsp;<code>newValue<\/code>&nbsp;in the subrectangle whose upper left coordinate is&nbsp;<code>(row1,col1)<\/code>&nbsp;and bottom right coordinate is&nbsp;<code>(row2,col2)<\/code>.<\/li><\/ul>\n\n\n\n<p>2.<code>&nbsp;getValue(int row, int col)<\/code><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Returns the current value of the coordinate&nbsp;<code>(row,col)<\/code>&nbsp;from&nbsp;the rectangle.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"SubrectangleQueries\",\"getValue\",\"updateSubrectangle\",\"getValue\",\"getValue\",\"updateSubrectangle\",\"getValue\",\"getValue\"]\n[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]\n<strong>Output<\/strong>\n<\/pre>\n\n\n<p>[null,1,null,5,5,null,10,5]<\/p>\n\n\n\n<p><strong>Explanation<\/strong>\nSubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);  \n\/\/ The initial rectangle (4&#215;3) looks like:\n\/\/ 1 2 1\n\/\/ 4 3 4\n\/\/ 3 2 1\n\/\/ 1 1 1\nsubrectangleQueries.getValue(0, 2); \/\/ return 1\nsubrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);\n\/\/ After this update the rectangle looks like:\n\/\/ 5 5 5\n\/\/ 5 5 5\n\/\/ 5 5 5\n\/\/ 5 5 5 \nsubrectangleQueries.getValue(0, 2); \/\/ return 5\nsubrectangleQueries.getValue(3, 1); \/\/ return 5\nsubrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);\n\/\/ After this update the rectangle looks like:\n\/\/ 5   5   5\n\/\/ 5   5   5\n\/\/ 5   5   5\n\/\/ 10  10  10 \nsubrectangleQueries.getValue(3, 1); \/\/ return 10\nsubrectangleQueries.getValue(0, 2); \/\/ return 5\n<\/p>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"SubrectangleQueries\",\"getValue\",\"updateSubrectangle\",\"getValue\",\"getValue\",\"updateSubrectangle\",\"getValue\"]\n[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]\n<strong>Output<\/strong>\n<\/pre>\n\n\n<p>[null,1,null,100,100,null,20]<\/p>\n\n\n\n<p><strong>Explanation<\/strong>\nSubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);\nsubrectangleQueries.getValue(0, 0); \/\/ return 1\nsubrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);\nsubrectangleQueries.getValue(0, 0); \/\/ return 100\nsubrectangleQueries.getValue(2, 2); \/\/ return 100\nsubrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);\nsubrectangleQueries.getValue(2, 2); \/\/ return 20\n<\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There will be at most&nbsp;<code>500<\/code>&nbsp;operations considering both methods:&nbsp;<code>updateSubrectangle<\/code>&nbsp;and&nbsp;<code>getValue<\/code>.<\/li><li><code>1 &lt;= rows, cols &lt;= 100<\/code><\/li><li><code>rows ==&nbsp;rectangle.length<\/code><\/li><li><code>cols == rectangle[i].length<\/code><\/li><li><code>0 &lt;= row1 &lt;= row2 &lt; rows<\/code><\/li><li><code>0 &lt;= col1 &lt;= col2 &lt; cols<\/code><\/li><li><code>1 &lt;= newValue, rectangle[i][j] &lt;= 10^9<\/code><\/li><li><code>0 &lt;= row &lt; rows<\/code><\/li><li><code>0 &lt;= col &lt; cols<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Simulation<\/strong><\/h2>\n\n\n\n<p>Update the matrix values.<\/p>\n\n\n\n<p>Time complexity: <br>Update: O(m*n), where m*n is the area of the sub-rectangle.<br>Query: O(1)<\/p>\n\n\n\n<p>Space complexity: O(rows*cols) <\/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 SubrectangleQueries {\npublic:\n  SubrectangleQueries(vector<vector<int>>& rectangle): \n    m_(rectangle) {}\n\n  void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {\n    for (int i = row1; i <= row2; ++i)\n      for (int j = col1; j <= col2; ++j)\n        m_[i][j] = newValue;\n  }\n\n  int getValue(int row, int col) {\n    return m_[row][col];\n  }\nprivate:\n  vector<vector<int>> m_;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Geometry<\/strong><\/h2>\n\n\n\n<p>For each update remember the region and value.<\/p>\n\n\n\n<p>For each query, find the newest updates that covers the query point. If not found, return the original value in the matrix.<\/p>\n\n\n\n<p>Time complexity:<br>Update: O(1)<br>Query: O(|U|), where |U| is the number of updates so far.<\/p>\n\n\n\n<p>Space complexity: O(|U|)<\/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 SubrectangleQueries {\npublic:\n  SubrectangleQueries(vector<vector<int>>& rectangle): \n    m_(rectangle) {}\n\n  void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {\n    updates_.push_front({row1, col1, row2, col2, newValue});\n  }\n\n  int getValue(int row, int col) {\n    for (const auto& u : updates_)\n      if (row >= u[0] && row <= u[2] &#038;&#038; col >= u[1] && col <= u[3])\n        return u[4];\n    return m_[row][col];\n  }\nprivate:\n  const vector<vector<int>>& m_;\n  deque<vector<int>> updates_;  \n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Implement the class&nbsp;SubrectangleQueries&nbsp;which receives a&nbsp;rows x cols&nbsp;rectangle as a matrix of integers in the constructor and supports two methods: 1.&nbsp;updateSubrectangle(int row1, int col1, int row2,&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,216,177,140,617],"class_list":["post-6909","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-matrix","tag-medium","tag-query","tag-update","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6909","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=6909"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6909\/revisions"}],"predecessor-version":[{"id":6911,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6909\/revisions\/6911"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6909"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6909"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6909"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}