Sponsored
Sponsored
The greedy approach involves iterating over the matrix and at each cell (i, j), filling it with the minimum of the current rowSum[i] and colSum[j]. This method works because as we fill the matrix, we can always satisfy both the row and column conditions by subtracting the filled value from each.
Move through the matrix, adjusting row and column sums at each step. This continues until we've filled the entire matrix, ensuring the integrity of both row and column sum conditions.
Time Complexity: O(m + n), where m and n are the lengths of rowSum and colSum respectively, as we're adjusting values once per index.
Space Complexity: O(m * n) for storing the matrix.
1#include <stdio.h>
2#include <stdlib.h>
3
4int** restoreMatrix(int* rowSum, int rowSize, int* colSum, int colSize, int** returnSize, int** returnColumnSizes) {
5 int** matrix = (int**)malloc(rowSize * sizeof(int*));
6 *returnColumnSizes = (int*)malloc(rowSize * sizeof(int));
7 *returnSize = rowSize;
8 for (int i = 0; i < rowSize; i++) {
9 matrix[i] = (int*)calloc(colSize, sizeof(int));
10 (*returnColumnSizes)[i] = colSize;
11 }
12 int i = 0, j = 0;
13 while (i < rowSize && j < colSize) {
14 int fill = rowSum[i] < colSum[j] ? rowSum[i] : colSum[j];
15 matrix[i][j] = fill;
16 rowSum[i] -= fill;
17 colSum[j] -= fill;
18 if (rowSum[i] == 0) i++;
19 if (colSum[j] == 0) j++;
20 }
21 return matrix;
22}The C implementation dynamically allocates a 2D array based on the given row and column sizes. It tracks and adjusts the row and column sums during matrix construction, continuing to iterate through the matrix until all sums are properly zeroed out.