Understood the approach and coded it myself. I have watched few of your videos and I observed that the way you explain things, wow man!! Huge respect.. Thanks!
Hi mik, i know it's weekend. If you get some free time, please continue segment tree playlist. Also if possible DP Concepts too Thank you again for your hard work
superb... Hint 1 - Find the smallest rowSum or colSum, and let it be x. Place that number in the grid, and subtract x from rowSum and colSum. Continue until all the sums are satisfied. but here we aren't finding the minimum rowSum or colSum right, or am i getting confused by their wording... also, what if the contraints were like there can't be any 0 element , OR, if row sum col sum isn't equal or there can be say 3 negative elements etc....
Solved it in O(N*M) time complexity. Here is the python implementation: class Solution: def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]: n, m = len(rowSum), len(colSum) res = [[0 for _ in range(m)] for _ in range(n)] for i in range(n): for j in range(m): res[i][j] = min(rowSum[i], colSum[j]) rowSum[i] -= res[i][j] colSum[j] -= res[i][j] return res
How do we come up with such a solution? I tried every possible way to code it like this but ended up solving nothing, then watched your solution and cursed myself.
While understanding I ignore the that matrix only contain non negative integer and below code working fine, but it also negative negative integer in matrix. Now here to understand the another approach to solve this public static int[][] restoreMatrix(int[] rowSum, int[] colSum) { int n = rowSum.length; int m = colSum.length; int[][] matrix = new int[n][m]; int s = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (j == m - 1) { matrix[i][j] = rowSum[i] - j; if (i < n - 1) s += rowSum[i] - j; } else { matrix[i][j] = 1; } } if (i == n - 1) { for (int j = 0; j < m; j++) { matrix[i][j] = colSum[j] - i; } } } matrix[n - 1][m - 1] = colSum[m - 1] - s; return matrix; }
class Solution { public int[][] restoreMatrix(int[] rowSum, int[] colSum) { int m = rowSum.length; int n = colSum.length; int i = 0; int j = 0; int[][] result = new int[m][n]; int minVal = Integer.MAX_VALUE; while (i < m && j < n) { minVal = Math.min(rowSum[i], colSum[j]); rowSum[i] -= minVal; colSum[j] -= minVal; result[i][j] = minVal; if (rowSum[i] == 0) { i++; // filling the i++ with default 0 } if (colSum[j] == 0) { j++; // filling the j++ with default 0 } } return result; } }
Good explanation but I thought the problem was very unintuitive. There are multiple solutions to the problem and looking at the examples it's hard to come up with the idea of taking the minimum and maintaining the order.
class Solution { public int[][] restoreMatrix(int[] rowSum, int[] colSum) { int m = rowSum.length; int n = colSum.length; int ans[][] = new int[m][n]; for(int i=0;i
bhaiya 3213 ka soln banaie na class Solution { public: vector restoreMatrix(vector& rowSum, vector& colSum) { int m=rowSum.size(); int n=colSum.size(); vector vec(m,vector(n,0)); for(int i=0;i
I got the idea from your video at very begining and paused the video and coded it in a one go . Credit goes to your efforts and dedication sir
Understood the approach and coded it myself. I have watched few of your videos and I observed that the way you explain things, wow man!! Huge respect..
Thanks!
Hi mik, i know it's weekend. If you get some free time, please continue segment tree playlist.
Also if possible DP Concepts too
Thank you again for your hard work
The playlist of DP is on the channel
smooth like butter
What a logical solution !!! 🙇
initial thoughts were to backtrack and generate the matrix. yet this approach simplifies.
coded just after listening 5 mins
superb...
Hint 1 - Find the smallest rowSum or colSum, and let it be x. Place that number in the grid, and subtract x from rowSum and colSum. Continue until all the sums are satisfied.
but here we aren't finding the minimum rowSum or colSum right, or am i getting confused by their wording...
also,
what if the contraints were like there can't be any 0 element ,
OR, if row sum col sum isn't equal
or there can be say 3 negative elements etc....
Bro you made this solution very easy to understand ---- thumbs Up !
lovely explaintaion
Excellent Explanation Brooo Thank you 🤩🤩
Solved it in O(N*M) time complexity. Here is the python implementation:
class Solution:
def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
n, m = len(rowSum), len(colSum)
res = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
res[i][j] = min(rowSum[i], colSum[j])
rowSum[i] -= res[i][j]
colSum[j] -= res[i][j]
return res
great video
Would be tough to come up with a solution during an interview.
class Solution {
public:
vector restoreMatrix(vector& rowSum, vector& colSum) {
int n=rowSum.size();
int m=colSum.size();
vector mat(n, vector(m));
for(int i=0;i
Nice video ❤
Segment tree video when?
Thank You Bhiya :)
Hey Mik,
Can you make a video on today's biweekly contest question 3 and question 4
can you please upload a vdo of upsolving today's biweekly leetcode contest
Thanks a lot bhaiya ❤❤
How do we come up with such a solution? I tried every possible way to code it like this but ended up solving nothing, then watched your solution and cursed myself.
bhaiya please make a playlist on question of binary search tree .
yes please
One doubt why TC is O(m+n) , if we are creating answer 2d vector and assigning it with 0 it will take m*n time so I think TC shouls be O(m*n)
first❤❤
Love you mik❤
While understanding I ignore the that matrix only contain non negative integer and below code working fine, but it also negative negative integer in matrix. Now here to understand the another approach to solve this
public static int[][] restoreMatrix(int[] rowSum, int[] colSum) {
int n = rowSum.length;
int m = colSum.length;
int[][] matrix = new int[n][m];
int s = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == m - 1) {
matrix[i][j] = rowSum[i] - j;
if (i < n - 1)
s += rowSum[i] - j;
} else {
matrix[i][j] = 1;
}
}
if (i == n - 1) {
for (int j = 0; j < m; j++) {
matrix[i][j] = colSum[j] - i;
}
}
}
matrix[n - 1][m - 1] = colSum[m - 1] - s;
return matrix;
}
Just watch the approach and code it my own.
class Solution {
public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
int m = rowSum.length;
int n = colSum.length;
int i = 0;
int j = 0;
int[][] result = new int[m][n];
int minVal = Integer.MAX_VALUE;
while (i < m && j < n) {
minVal = Math.min(rowSum[i], colSum[j]);
rowSum[i] -= minVal;
colSum[j] -= minVal;
result[i][j] = minVal;
if (rowSum[i] == 0) {
i++;
// filling the i++ with default 0
}
if (colSum[j] == 0) {
j++;
// filling the j++ with default 0
}
}
return result;
}
}
Good explanation but I thought the problem was very unintuitive. There are multiple solutions to the problem and looking at the examples it's hard to come up with the idea of taking the minimum and maintaining the order.
if someone is from Machine Learning, they can relate this question as confusion Matrix 😁😁😁
thanks
class Solution {
public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
int m = rowSum.length;
int n = colSum.length;
int ans[][] = new int[m][n];
for(int i=0;i
I am having doubt as how it gurantees the solution.
I was trying to solve this problem from two hours but couldn't get this approach 😔.
what if we want to find out the number of such matrix possible... how can we approach in that case ?
Thanks 😊
We can also solve this using priority queue just take smallest element and subtract it from rowSum and colsum
Bte segment tree videos when?
yes maine bhi wahi socha tha starting me.
Op
bhaiya ye greedy approach kam kyu ker raha iska proof hai koi?
bhaiya 3213 ka soln banaie na
class Solution {
public:
vector restoreMatrix(vector& rowSum, vector& colSum) {
int m=rowSum.size();
int n=colSum.size();
vector vec(m,vector(n,0));
for(int i=0;i
sir me khud se logic nhi bna pata
kya hi bekar qs hai yr ekdam bhi intuition nhi aya
same here bro