{"id":7445,"date":"2020-10-03T16:14:45","date_gmt":"2020-10-03T23:14:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7445"},"modified":"2020-10-03T16:39:32","modified_gmt":"2020-10-03T23:39:32","slug":"leetcode-1605-find-valid-matrix-given-row-and-column-sums","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1605-find-valid-matrix-given-row-and-column-sums\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1605. Find Valid Matrix Given Row and Column Sums"},"content":{"rendered":"\n

You are given two arrays rowSum<\/code> and colSum<\/code> of non-negative integers where rowSum[i]<\/code> is the sum of the elements in the ith<\/sup><\/code> row and colSum[j]<\/code> is the sum of the elements of the jth<\/sup><\/code> column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.<\/p>\n\n\n\n

Find any matrix of non-negative<\/strong> integers of size rowSum.length x colSum.length<\/code> that satisfies the rowSum<\/code> and colSum<\/code> requirements.<\/p>\n\n\n\n

Return a 2D array representing any<\/strong> matrix that fulfills the requirements<\/em>. It’s guaranteed that at least one <\/strong>matrix that fulfills the requirements exists.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> rowSum = [3,8], colSum = [4,7]\nOutput:<\/strong> [[3,0],\n         [1,7]]\nExplanation:<\/strong>\n0th row: 3 + 0 = 0 == rowSum[0]\n1st row: 1 + 7 = 8 == rowSum[1]\n0th column: 3 + 1 = 4 == colSum[0]\n1st column: 0 + 7 = 7 == colSum[1]\nThe row and column sums match, and all matrix elements are non-negative.\nAnother possible matrix is: [[1,2],\n                             [3,5]]\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rowSum = [5,7,10], colSum = [8,6,8]\nOutput:<\/strong> [[0,5,0],\n         [6,1,0],\n         [2,0,8]]\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rowSum = [14,9], colSum = [6,9,8]\nOutput:<\/strong> [[0,9,5],\n         [6,0,3]]\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rowSum = [1,0], colSum = [1]\nOutput:<\/strong> [[1],\n         [0]]\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rowSum = [0], colSum = [0]\nOutput:<\/strong> [[0]]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= rowSum.length, colSum.length <= 500<\/code><\/li>
  • 0 <= rowSum[i], colSum[i] <= 108<\/sup><\/code><\/li>
  • sum(rows) == sum(columns)<\/code><\/li><\/ul>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    Let a = min(row[i], col[j]), m[i][j] = a, row[i] -= a, col[j] -=a<\/p>\n\n\n\n
    Time complexity: O(m*n)
    Space complexity: O(m*n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector> restoreMatrix(vector& rowSum, vector& colSum) {\n    const int m = rowSum.size();\n    const int n = colSum.size();\n    vector> ans(m, vector(n));\n    for (int i = 0; i < m; ++i)\n      for (int j = 0; j < n; ++j) {\n        ans[i][j] = min(rowSum[i], colSum[j]);\n        rowSum[i] -= ans[i][j];\n        colSum[j] -= ans[i][j];\n      }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the ith row and colSum[j] is the sum of the elements of the jth column of a…<\/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,216,177],"class_list":["post-7445","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-matrix","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7445","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=7445"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7445\/revisions"}],"predecessor-version":[{"id":7447,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7445\/revisions\/7447"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}