Find Valid Matrix Given Row and Column Sums - Leetcode 1605 - Python

[@HuyLe-zx8ko]

I feel stupid

[@yang5843]

Neetcode? More like Elitecode

[@DeathSugar]

elite aka leet is literally the thing where you write your solutions

[@sojwalgosavi4406]

for java users, intialize currentColSum as in long so it wont overflow the int Thanks for this intuitive solution

[@anandsahoo3711]

thanks bro i was not able to pass the last test case

[@glenwu3523]

Man... Wish one day I could solve these problems like you did in an interview....

[@AnandKumar-kz3ls]

your first solution was brilliant

[@freecourseplatformenglish2829]

Actually It was 2nd solution that came to my mind first. Thanks for detailed explainiation.

[@saswatmishra4055]

How to come up with thse intuitions? I am trying to solve but these problems leave me completely blank, i tried for 10mins and gave up ):

[@chrischika7026]

its greedy you cant really come up with it.

[@Its_Shubham_Negi]

@@chrischika7026 exactly

[@neks2081]

more practice, start doing more greedy problems, look and understand solutions deeply

[@ZeEduardo95]

Doing more problems. Tracking where you're good at and improving the topics where you suck. Researching harder exercises when you think you are good at something also helps. Try to be as balanced as possible and dominate as many areas as you can. Being self aware and auto critical helps too. Keep going!

[@thehappydeveloperguide]

@@ZeEduardo95 I think he asked what is the intuition for the current problem, how he come to the solution, something like proof in maths if i'm not wrong. You can easily solve many problems without understanding it fully but you practice a lot in Leetcode and just solve it when you see the x100 times the same problem. I think there is more logic then the greedy paradigm right here, the row sum which is exceeding the current column get propagated to the other columns and I think we stop when there is no remainder left, which is achieved on the last column. So the greedy part is just a "part" from the whole logic I am also struggling to understand why this exactly works, so deeper explanation will be good :). Otherwise perfect advices from you. Thank you !

[@KnightMirkoYo]

Thank you so much, your daily explanations are invaluable

[@ashishkarn9283]

The last solution is really a brilliant idea.

[@MP-ny3ep]

Phenomenal explanation as always. Thank you !!!

[@LemesaElias]

I just realized I should do matrix problems more often.

[@yashshukla1637]

Inner while loop is not needed ``` class Solution: def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]: ROWS = len(rowSum) COLS = len(colSum) result = [] for i in range(0, ROWS): row = [] for j in range(0, COLS): row.append(0) result.append(row) ## initialize rows for row in range(0,ROWS): result[row][0] = rowSum[row] for col in range(0, COLS): current_col_sum = 0 # get the whole col sum for row in range(0, ROWS): current_col_sum += result[row][col] if current_col_sum > colSum[col]: diff = current_col_sum - colSum[col] max_shift = min(result[row][col], diff) result[row][col] -= max_shift result[row][col + 1] += max_shift current_col_sum -= max_shift return result ```

[@juanmacias5922]

I filled the first column with the max, and I was keeping a curr count to populate the next column with the overflow.

[@abhijeetsarkar7541]

that's a good idea too!

[@galkk3]

my solution, it is more like the second solution that you talked about, same TC and SC: ROWS, COLS = len(rowSum), len(colSum) grid = [[0] * COLS for _ in range(ROWS)] while ROWS > 0 and COLS > 0: minRow = min(rowSum) minCol = min(colSum) rowIndex = rowSum.index(minRow) colIndex = colSum.index(minCol) if minRow < minCol: rowSum[rowIndex] = float("inf") colSum[colIndex] -= minRow grid[rowIndex][colIndex] = minRow ROWS -= 1 else: rowSum[rowIndex] -= minCol colSum[colIndex] = float("inf") grid[rowIndex][colIndex] = minCol COLS -= 1 return grid

[@anandsrikumar007]

Awesome explanation bro. I solved it.

[@justanuhere]

you have awesome explanations

[@bhuvan9956]

Easier way to write first approach ROWS = len(rowSum) COLS = len(colSum) currColSum = sum(rowSum) matrix = [[0] * COLS for _ in range(ROWS)] # put all rowSum values in their corresponding row # in the first column to balance it out to other columns for i in range(ROWS): matrix[i][0] = rowSum[i] for col in range(COLS - 1): extraSum = currColSum - colSum[col] # for the next column so we dont have to calcuate the # next col's sum total current Sum again currColSum = extraSum for row in range(ROWS): if extraSum == 0: break minValue = min(extraSum, matrix[row][col]) matrix[row][col] -= minValue extraSum -= minValue matrix[row][col + 1] += minValue return matrix

[@sddkmweervra]

11:50

[@DeathSugar]

Come up with the second soultuion and it was even cleaner. It's named monte-carlo method if I remember correctly

[@sidforreal]

I kinda like the second approach more, felt more logical

[@abhishekkumar-fe8lw]

Getting wrong answer for the last tescases which consists of 1e8 in all cells,i am not able to see the whole output class Solution { public int[][] restoreMatrix(int[] rowSum, int[] colSum) { int n=rowSum.length; int m=colSum.length; int[][] ans=new int[n][m]; for(int i=0;i

[@028_ds_khushi_bohra2]

same

[@ParthCoool]

+1

[@NeetCodeIO]

Huh, now I'm curious because your code looks correct. I don't see anywhere that an overflow could occur either, that's strange.

[@NeetCodeIO]

Actually based on a solution someone else shared I think cursum and diff should be doubles / long. While it's true rowSum param is integers, the sum of rowSum could overflow a 32bit int.

[@jessesinger4790]

Very nice

[@corrogist692]

I converted the two inputs as minheaps and keep popping and pushing back their val differences to the heap with a larger value, does this make the time complexity faster/slower?

[@corrogist692]

##Heres how i did it: class Solution: def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]: #Create res matrix m, n = len(rowSum), len(colSum) res=[[0] * n for _ in range(m)] #maintain two min heaps rowheap=[(s, i) for i, s in enumerate(rowSum)] heapq.heapify(rowheap) colheap=[(s, i) for i, s in enumerate(colSum)] heapq.heapify(colheap) while rowheap and colheap: rowval, rowidx=heapq.heappop(rowheap) colval, colidx=heapq.heappop(colheap) res[rowidx][colidx]=min(rowval, colval) if rowval>colval: heapq.heappush(rowheap, (rowval-colval, rowidx)) elif colval>rowval: heapq.heappush(colheap, (colval-rowval, colidx)) return res

[@pastori2672]

i felt insane after getting the most optimal solution first try

[@pastori2672]

you are insane

[@pastori2672]

@pastori2672 you think so ?

[@pastori2672]

@pastori2672 definitely

[@Its_Shubham_Negi]

@@pastori2672 self-talk 😆

[@yuvrajmalhotra9276]

@@pastori2672 is it Self-obsession or you seen fight club ?

[@abhilashpatel6852]

I came up with the second one and believe now that first one is better than mine 😅

[@michaelroditis1952]

Second solution is faster because you don't need to pass through all cells, even if they're the same complexity

[@qulinxao]

class Solution: def restoreMatrix(self, r: List[int], c: List[int]) -> List[List[int]]: m=[[0]*len(c)for _ in range(len(r))] g=[[(v,e)for e,v in enumerate(b)if v]for b in [r,c]] for v in g:heapify(v) while g[0]: m[g[0][0][1]][g[1][0][1]]=(z:=min(g[0][0],g[1][0])[0]) for w in g: if(t:=w[0][0]-z): heapreplace(w,(t,w[0][1])) else: heappop(w) return m

[@yang5843]

My logic might be easier to understand class Solution { public int[][] restoreMatrix(int[] rowSum, int[] colSum) { int[][] rc = new int[rowSum.length][colSum.length]; for (int i=0;i

[@harshadevarakonda7965]

May I know why you used double over long datatype and when double is replaced by long the solution isn't getting accepted.

[@chaitanyasharma6270]

public class Solution { public int[][] RestoreMatrix(int[] rowSum, int[] colSum) { int [][] a=new int[rowSum.Length][]; for(int i=0;i

[@0ManPiano0]

damn... I feel dumb not being even able to come up with a working solution...

[@fauzudheenabdulhameed8399]

Is n't this the easiest way to do it, Just find the min(rowSum, colSum) and append it to res. Also alter the input arrays. class Solution: def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]: res = [] for i in range(len(rowSum)): row = [] for j in range(len(colSum)): curr = min(rowSum[i], colSum[j]) rowSum[i] -= curr colSum[j] -= curr row.append(curr) res.append(row) return res but i came up with this just by looking the examples, might not be intuitive in anyway.

[@LemesaElias]

It's follows the same approach as the code in the editorial but still it's really a brilliant approach.

[@moabd7575]

EDIT: never mind, i used long long for "diff" and "max_shift" and it worked getting integer overflow with C++ in the variable "curr_col_max" i used long long but i get negative values in the result array any solution?

[@eslamwageh4461]

did u find one ?

[@chandlerbing8164]

only Simple for you cause you come from math background.

[@chien-yuyeh9386]

🎉🎉First 😂

[@thunderstorm-d2c]

Matrix week😂

[@irfanmohammad2132]

before 2025

[@anmolgangwal9236]

no offence but 2nd solution seems more easier😂