aboutsummaryrefslogtreecommitdiff
path: root/find_valid_matrix_row_col.py
blob: 06ddf061feb2e8399aaa3699aae46e7091e75c94 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 1605. Find Valid Matrix Given Row and Column Sums

"""
given two arrays 'rowSum' and 'colSum' of non negative integers where
'rowSum[i]' is the sum of the elements in the i'th row and 'colSum[i]' is the
sum of the elemtns in the i'th row and 'colSum[j]' is the sum of the elemtns
of the j'th column of a 2d matrix. in other words, you do not know the
elements of the matrix, but you do know the sumes of each row and column.
"""


class Solution(object):
    def restoreMatrix(self, rowSum, colSum):
        """
        :type rowSum: List[int]
        :type colSum: List[int]
        :rtype: List[List[int]]
        """
        m, n = len(rowSum), len(colSum)
        ans = [[0] * n for i in range(m)]
        for i in range(m):
            for j in range(n):
                ans[i][j] = min(rowSum[i], colSum[j])
                rowSum[i] -= ans[i][j]
                colSum[j] -= ans[i][j]
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.restoreMatrix(rowSum=[3, 8], colSum=[4, 7]))
    print(obj.restoreMatrix(rowSum=[5, 7, 10], colSum=[8, 6, 8]))