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!
@@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 !
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 ```
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?
##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
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
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
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.
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?
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
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.
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
I feel stupid
Neetcode? More like Elitecode
elite aka leet is literally the thing where you write your solutions
for java users, intialize currentColSum as in long so it wont overflow the int
Thanks for this intuitive solution
thanks bro i was not able to pass the last test case
Man... Wish one day I could solve these problems like you did in an interview....
your first solution was brilliant
Actually It was 2nd solution that came to my mind first. Thanks for detailed explainiation.
Thank you so much, your daily explanations are invaluable
Phenomenal explanation as always. Thank you !!!
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 ):
its greedy you cant really come up with it.
@@chrischika7026 exactly
more practice, start doing more greedy problems, look and understand solutions deeply
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!
@@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 !
The last solution is really a brilliant idea.
Awesome explanation bro. I solved it.
you have awesome explanations
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
11:50
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
```
I filled the first column with the max, and I was keeping a curr count to populate the next column with the overflow.
that's a good idea too!
Come up with the second soultuion and it was even cleaner. It's named monte-carlo method if I remember correctly
I just realized I should do matrix problems more often.
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?
##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
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
I kinda like the second approach more, felt more logical
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
same
+1
Huh, now I'm curious because your code looks correct. I don't see anywhere that an overflow could occur either, that's strange.
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.
Very nice
I came up with the second one and believe now that first one is better than mine 😅
Second solution is faster because you don't need to pass through all cells, even if they're the same complexity
i felt insane after getting the most optimal solution first try
you are insane
@pastori2672 you think so ?
@pastori2672 definitely
@@pastori2672 self-talk 😆
@@pastori2672 is it Self-obsession or you seen fight club ?
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?
did u find one ?
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
public class Solution {
public int[][] RestoreMatrix(int[] rowSum, int[] colSum) {
int [][] a=new int[rowSum.Length][];
for(int i=0;i
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.
It's follows the same approach as the code in the editorial but still it's really a brilliant approach.
🎉🎉First 😂
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
May I know why you used double over long datatype and when double is replaced by long the solution isn't getting accepted.
only Simple for you cause you come from math background.
damn... I feel dumb not being even able to come up with a working solution...
Matrix week😂
before 2025
no offence but 2nd solution seems more easier😂