Find valid matrix given row and column sums

Array Greedy Matrix

82.7% acceptance

Feb 25, 2026

2197

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the ith row and colSum[j] is the sum of the elements of the jth column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column. Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements. Return a 2D array representing any matrix that fulfills the requirements. It's guaranteed that at least one matrix that fulfills the requirements exists.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn restore_matrix(row_sum: Vec<i32>, col_sum: Vec<i32>) -> Vec<Vec<i32>> {
    let r = row_sum.len();
    let c = col_sum.len();
    let mut rs = row_sum.clone();
    let mut cs = col_sum.clone();
    let mut mat = vec![vec![0i32; c]; r];
    for i in 0..r {
      for j in 0..c {
        let val = rs[i].min(cs[j]);
        mat[i][j] = val;
        rs[i] -= val;
        cs[j] -= val;
      }
    }
    mat
  }
}