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 !
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
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 ```
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.
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
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?
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
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
