{"id":5820,"date":"2019-11-09T22:55:04","date_gmt":"2019-11-10T06:55:04","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5820"},"modified":"2019-11-13T02:07:15","modified_gmt":"2019-11-13T10:07:15","slug":"leetcode-1253-reconstruct-a-2-row-binary-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1253-reconstruct-a-2-row-binary-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1253. Reconstruct a 2-Row Binary Matrix"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1252 1253 1254 1255 Weekly Contest 162  - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/1XMpzhFUvco?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given the following details of a matrix with&nbsp;<code>n<\/code>&nbsp;columns and&nbsp;<code>2<\/code>&nbsp;rows :<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The matrix is a binary matrix, which means each element in the matrix can be&nbsp;<code>0<\/code>&nbsp;or&nbsp;<code>1<\/code>.<\/li><li>The sum of elements of the 0-th(upper) row is given as&nbsp;<code>upper<\/code>.<\/li><li>The sum of elements of the 1-st(lower) row is given as&nbsp;<code>lower<\/code>.<\/li><li>The sum of elements in the i-th column(0-indexed) is&nbsp;<code>colsum[i]<\/code>, where&nbsp;<code>colsum<\/code>&nbsp;is given as an integer array with length&nbsp;<code>n<\/code>.<\/li><\/ul>\n\n\n\n<p>Your task is to reconstruct the matrix with&nbsp;<code>upper<\/code>,&nbsp;<code>lower<\/code>&nbsp;and&nbsp;<code>colsum<\/code>.<\/p>\n\n\n\n<p>Return it as a 2-D integer array.<\/p>\n\n\n\n<p>If there are more than one valid solution, any of them will be accepted.<\/p>\n\n\n\n<p>If no valid solution exists, return an empty 2-D array.<\/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> upper = 2, lower = 1, colsum = [1,1,1]\n<strong>Output:<\/strong> [[1,1,0],[0,0,1]]\n<strong>Explanation: <\/strong>[[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.\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> upper = 2, lower = 3, colsum = [2,2,1,1]\n<strong>Output:<\/strong> []\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]\n<strong>Output:<\/strong> [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= colsum.length &lt;= 10^5<\/code><\/li><li><code>0 &lt;= upper, lower &lt;= colsum.length<\/code><\/li><li><code>0 &lt;= colsum[i] &lt;= 2<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy?<\/strong><\/h2>\n\n\n\n<p>Two passes:<br>first pass, only process sum = 2, upper = 1, lower = 1<br>second pass, only process sum = 1, whoever has more leftover, assign 1 to that row.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/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 Solution {\npublic:\n  vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {\n    const int n = colsum.size();\n    vector<vector<int>> a(2, vector<int>(n));\n    for (int i = 0; i < n; ++i)\n      if (colsum[i] == 2) {\n        a[0][i] = a[1][i] = 1;\n        --upper;\n        --lower;\n      }\n    \n    for (int i = 0; i < n; ++i)\n      if (colsum[i] == 1)\n        if (upper > lower) {\n          a[0][i] = 1;\n          --upper;\n        } else {\n          a[1][i] = 1;\n          --lower;\n        }\n    if (upper != 0 || lower != 0) return {};\n    return a;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given the following details of a matrix with&nbsp;n&nbsp;columns and&nbsp;2&nbsp;rows : The matrix is a binary matrix, which means each element in the matrix can be&nbsp;0&nbsp;or&nbsp;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":[51],"tags":[88,177,376,385],"class_list":["post-5820","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-on","tag-reconstruct","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5820","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=5820"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5820\/revisions"}],"predecessor-version":[{"id":5829,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5820\/revisions\/5829"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5820"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5820"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}