diff options
author | Jack Sangdahl <[email protected]> | 2024-07-20 01:21:39 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-20 01:21:39 -0600 |
commit | 20318810d2b118ecf1931909cdbd36c87f0951b5 (patch) | |
tree | 2fa84c1ae439cc16d47eff15805f613be524bb09 | |
parent | 33b75b757bc8d541a630c1b623870ff914fe2974 (diff) | |
download | leetcode-20318810d2b118ecf1931909cdbd36c87f0951b5.tar.gz leetcode-20318810d2b118ecf1931909cdbd36c87f0951b5.zip |
1605. find valid matrix given row and column sums
-rw-r--r-- | find_valid_matrix_row_col.c | 53 | ||||
-rw-r--r-- | find_valid_matrix_row_col.py | 32 |
2 files changed, 85 insertions, 0 deletions
diff --git a/find_valid_matrix_row_col.c b/find_valid_matrix_row_col.c new file mode 100644 index 0000000..5f5213b --- /dev/null +++ b/find_valid_matrix_row_col.c @@ -0,0 +1,53 @@ +// 1605. Find Valid Matrix Given Row and Column Sums +#include "leetcode.h" + +/* + * 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. + */ + +int **restoreMatrix(int *rowSum, int rowSumSize, int *colSum, int colSumSize, + int *returnSize, int **returnColumnSizes) { + int *store = (int *)malloc(rowSumSize * colSumSize * sizeof(*store)); + int **ans = (int **)malloc(rowSumSize * sizeof(*ans)); + for (int i = 0; i < rowSumSize; i++) + ans[i] = store + i * colSumSize; + *returnSize = rowSumSize; + *returnColumnSizes = (int *)malloc(rowSumSize * sizeof(*returnColumnSizes)); + for (int i = 0; i < rowSumSize; i++) + (*returnColumnSizes)[i] = colSumSize; + for (int i = 0; i < rowSumSize; i++) + for (int j = 0; j < colSumSize; j++) { + ans[i][j] = fmin(rowSum[i], colSum[j]); + rowSum[i] -= ans[i][j]; + colSum[j] -= ans[i][j]; + } + return ans; +} + +int main() { + int rs1[] = {3, 8}, cs1[] = {4, 7}, res1, rcs1[] = {2, 2}; + int rs2[] = {5, 7, 10}, cs2[] = {8, 6, 8}, res2, rcs2[] = {3, 3, 3}; + int **rm1 = restoreMatrix(rs1, ARRAY_SIZE(rs1), cs1, ARRAY_SIZE(cs1), &res1, + (int **)rcs1); + int **rm2 = restoreMatrix(rs2, ARRAY_SIZE(rs2), cs2, ARRAY_SIZE(cs2), &res2, + (int **)rcs2); + for (int i = 0; i < res1; i++) { + for (int j = 0; j < rcs1[i]; j++) + printf("%d ", rm1[i][j]); + printf("\n"); + } + for (int i = 0; i < res2; i++) { + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", rm2[i][j]); + printf("\n"); + } + for (int i = 0; i < res1; i++) + free(rm1[i]); + for (int i = 0; i < res2; i++) + free(rm2[i]); + free(rm1), free(rm2); +} diff --git a/find_valid_matrix_row_col.py b/find_valid_matrix_row_col.py new file mode 100644 index 0000000..06ddf06 --- /dev/null +++ b/find_valid_matrix_row_col.py @@ -0,0 +1,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])) |