1605. Find Valid Matrix Given Row and Column Sums

T: O(mn)
S: O(mn)

refer to Neetcode one:

class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length;
        int n = colSum.length;
        long[][] res = new long[m][n];

        for (int row = 0; row < m; row++) {
            res[row][0] = rowSum[row];
        }
        for (int col = 0; col < n; col++) {
            int curColSum = 0;
            for (int row = 0; row < m; row++) {
                curColSum += res[row][col];
           
                if (curColSum > colSum[col]) {
                    long diff = curColSum - colSum[col];
                    long shift = Math.min(res[row][col], diff);
                    res[row][col] -= shift;
                    res[row][col+1] += shift;
                    curColSum -= shift;
                }
            }
        }
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = (int) res[i][j];
            }
        }
        return result;
    }
}

/**

fulfill rowsum first ->
   4. 7
3  3 
8  8

then we can try to fullfill colsum
so for first col, now col_sum = 11, but we only want 4
11 - 4 = 7 so 7 need to move to next col

so first col, first row, we move
min(3, 7) -> move 3 to next col
   4. 7
3     3
8  8
col_sum = 11 - 3 = 8 

go to next row, 
first col, second row
8 - 4 = 4 -> need 4 to move to next col
   4. 7
3     3
8  4. 4

-> then it completed! because we qurateen there must be one solution to this matrix
and a interesting fact is rowSum == colSum. (3+8 = 4+7) = 11

T: O(mn)
S: O(mn)
 */