_1605. Find Valid Matrix Given Row and Column Sums.md

1605. Find Valid Matrix Given Row and Column Sums

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 20, 2024

Last updated : July 20, 2024

---

Related Topics : Array, Greedy, Matrix

Acceptance Rate : 83.06 %

---

Not the most efficient but was the most straightforwards to type up. To improve, we could keep track of which row to start totaling from so we don't have to "tally" the rows that the rest will already be zero for.

Adjusted for this in Version 2.

---

Solutions

• m1605 Daily v1.py
• m1605 Daily v2.py

Python

m1605 Daily v1.py

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        output = [[rowSum[x]] + [0] * (len(colSum) - 1) for x in range(len(rowSum))]

        for c in range(len(colSum) - 1) :
            total = 0
            indx = 0

            while indx < len(rowSum) and total < colSum[c] :
                total += output[indx][c]
                indx += 1

            indx -= 1

            output[indx][c + 1] = total - colSum[c]
            output[indx][c] -= output[indx][c + 1]

            indx += 1

            for i in range(indx, len(rowSum)) :
                output[i][c + 1] = output[i][c]
                output[i][c] = 0

        return output

m1605 Daily v2.py

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        output = [[rowSum[x]] + [0] * (len(colSum) - 1) for x in range(len(rowSum))]

        minRow = 0
        for c in range(len(colSum) - 1) :
            total = 0
            indx = minRow

            while indx < len(rowSum) and total < colSum[c] :
                total += output[indx][c]
                indx += 1

            indx -= 1
            minRow = indx

            output[indx][c + 1] = total - colSum[c]
            output[indx][c] -= output[indx][c + 1]

            indx += 1

            for i in range(indx, len(rowSum)) :
                output[i][c + 1] = output[i][c]
                output[i][c] = 0

        return output