LeetCode
comments powered by Disqus
Editorial: LeetCode 1605 Find Valid Matrix Given Row and Column Sums
https://leetcode.com/problems/find-valid-matrix-given-row-and-column-sums/ from Google
Since the problem claims that there must be an answer, I try to use greedy algorithm from cell to cell.
1class Solution {
2public:
3 vector<vector<int>> restoreMatrix(vector<int>& rs, vector<int>& cs) {
4 int R = rs.size(), C = cs.size();
5 vector<vector<int>> ret = vector(R, vector<int>(C));
6 for (int i=0; i<R; i++) {
7 for (int j=0; j<C; j++) {
8 int x = min(rs[i], cs[j]);
9 rs[i] -= x;
10 cs[j] -= x;
11 ret[i][j] = x;
12 }
13 }
14 return ret;
15 }
16};