LeetCode Entry

1605. Find Valid Matrix Given Row and Column Sums

20.07.2024 medium 2024 kotlin rust

Matrix from rows and cols sums

1605. Find Valid Matrix Given Row and Column Sums medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/676

Problem TLDR

Matrix from rows and cols sums #medium

Intuition

Let’s try to build such a matrix with our bare hands, pen and paper:

I have noticed some interesting facts about this problem:

• there are several valid matrices, all depend on the numbers you choose first
• you have to choose the minimum between the row and column sums, otherwise the sum became bigger than needed
• you can move row by row or column by column
• the more robust strategy is to take as bigger number as possible first, instead of choosing from some of the lower valid values: you don’t have to backtrack then

Approach

• Use an array initializer in Kotlin

Complexity

• Time complexity: \(O(nm)\)

• Space complexity: \(O(nm)\)

Code

    fun restoreMatrix(rowSum: IntArray, colSum: IntArray) =
        Array(rowSum.size) { y ->
            IntArray(colSum.size) { x ->
                val v = min(rowSum[y], colSum[x])
                rowSum[y] -= v; colSum[x] -= v; v }}

    pub fn restore_matrix(mut row_sum: Vec<i32>, mut col_sum: Vec<i32>) -> Vec<Vec<i32>> {
        let mut res = vec![vec![0; col_sum.len()]; row_sum.len()];
        for y in 0..res.len() { for x in 0..res[0].len() {
            let v = row_sum[y].min(col_sum[x]);
            row_sum[y] -= v; col_sum[x] -= v; res[y][x] = v
        }}; res
    }