{"id":4806,"date":"2019-02-09T11:32:10","date_gmt":"2019-02-09T19:32:10","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4806"},"modified":"2019-02-09T11:56:59","modified_gmt":"2019-02-09T19:56:59","slug":"leetcode-73-set-matrix-zeroes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-73-set-matrix-zeroes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 73. Set Matrix Zeroes"},"content":{"rendered":"\n<p>Given a&nbsp;<em>m<\/em>&nbsp;x&nbsp;<em>n<\/em>&nbsp;matrix, if an element is 0, set its entire row and column to 0. Do it&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/In-place_algorithm\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>in-place<\/strong><\/a>.<\/p>\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[\n&nbsp; [1,1,1],\n&nbsp; [1,0,1],\n&nbsp; [1,1,1]\n]\n<strong>Output:<\/strong> \n[\n&nbsp; [1,0,1],\n&nbsp; [0,0,0],\n&nbsp; [1,0,1]\n]\n<\/pre>\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[\n&nbsp; [0,1,2,0],\n&nbsp; [3,4,5,2],\n&nbsp; [1,3,1,5]\n]\n<strong>Output:<\/strong> \n[\n&nbsp; [0,0,0,0],\n&nbsp; [0,4,5,0],\n&nbsp; [0,3,1,0]\n]\n<\/pre>\n\n\n\n<p><strong>Follow up:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A straight forward solution using O(<em>m<\/em><em>n<\/em>) space is probably a bad idea.<\/li><li>A simple improvement uses O(<em>m<\/em>&nbsp;+&nbsp;<em>n<\/em>) space, but still not the best solution.<\/li><li>Could you devise a constant space solution?<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1<\/strong><\/h2>\n\n\n\n<p>Use two arrays to track whether the i-th row \/ j-th column need to be zeroed.<\/p>\n\n\n\n<p>Time complexity: O(mn)<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++\">\nclass Solution {\npublic:\n  void setZeroes(vector<vector<int>>& matrix) {\n    const int m = matrix.size();\n    const int n = matrix[0].size();\n    vector<int> rows(m);\n    vector<int> cols(n);\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j) {\n        rows[i] |= (matrix[i][j] == 0);\n        cols[j] |= (matrix[i][j] == 0);\n      }\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j)\n        if (rows[i] || cols[j]) matrix[i][j] = 0;        \n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2<\/strong><\/h2>\n\n\n\n<p>Use the first row \/ first col to indicate whether the i-th row \/ j-th column need be zeroed.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  void setZeroes(vector<vector<int>>& matrix) {\n    const int m = matrix.size();\n    const int n = matrix[0].size();\n    \n    bool col0 = false;\n    bool row0 = false;\n    \n    for (int i = 0; i < m; ++i) \n      col0 |= (matrix[i][0] == 0);\n    for (int j = 0; j < n; ++j) \n      row0 |= (matrix[0][j] == 0);\n    \n    for (int i = 1; i < m; ++i)\n      for (int j = 1; j < n; ++j)\n        if (matrix[i][j] == 0)\n          matrix[0][j] = matrix[i][0] = 0;      \n    \n    for (int i = 1; i < m; ++i)\n      for (int j = 1; j < n; ++j)\n        if (matrix[i][0] == 0 || matrix[0][j] == 0)\n          matrix[i][j] = 0;\n    \n    if (row0)\n      for (int j = 0; j < n; ++j) \n        matrix[0][j] = 0;\n    \n    if (col0)\n      for (int i = 0; i < m; ++i) \n        matrix[i][0] = 0;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;m&nbsp;x&nbsp;n&nbsp;matrix, if an element is 0, set its entire row and column to 0. Do it&nbsp;in-place. Example 1: Input: [ &nbsp; [1,1,1], &nbsp; [1,0,1],&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[463,273,92],"class_list":["post-4806","post","type-post","status-publish","format-standard","hentry","category-array","tag-constant-space","tag-in-place","tag-o1","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4806","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=4806"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4806\/revisions"}],"predecessor-version":[{"id":4809,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4806\/revisions\/4809"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4806"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4806"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4806"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}