For someone who is wondering what he means by the " more restrictive part" : (Read Along) Let us say we have a row, as below and we are at the arrow mark downward(denoted by a V) V 0 1 1 1 0 Now let us say the row above this is 0 0 1 1 0 So together let us say we have
V 1 0 0 1 1 0 2 0 1 1 1 0 Just reminding you that we need to calculate the value of the second row 4th element If we talk about the second row 'lb' will hold the value 1, which denotes that the line of ones stretches from the 4th element to the first element in this row. So the left bound is 1 But, if we have a row above it(row 1) such that the length of the rows of one is less that row 2 the rectangle will have to be of that smaller length. This basically is the common area that we are taking. Read the above line again and you will get it! Now we simply take the max because we want the rightmost bound on lb. Hope this helps. If anyone still has a doubt feel free to ask!!!! Great explanation by the way!!
It still doesn't make sense to me. Suppose we have this: 0 0 0 1 0 0 1 1 1 0 And we are on 2nd row and 4th element. According to the algo, the lb of this will be 4 since the width of the upper two rectangle is just 1. So effective we will have a reactangle of size 2x1 which has area 2. But there is a larger reactangle possible from the second row with 3 1s. What is wrong here? What i mean is, when we calculate the area of a reactangle using dph, dpl, dpr for some particular cell i,j in the grid, what does this tell us? The maximum area up until this cell? If so, then why do we need a right bound as that will go past that cell?
I've been watching your videos to help with my interview prep and they have been super helpful so far! I especially like how you write 1-2 lines of code then explain it which is well-suited for the interview process. Moreover, I appreciate have well-articulated your explanations are. I was wondering which tools do you use to do the transitions when refactoring and highlighting certain parts of your code? And the tools for the diagrams you use?
Thanks for your clear explanation ! What is your strategy to come up with the DP table design in the first place? I was asked this in an initial screening interview and thrown off guard.
Why do we need to find the left and the right bound? Why can't we just keep a running max of the area of the largest reactangle with its bottom right corner at i,j ? Similar to the leetcode question max square (see ericchto's video for this)
How one comes to the idea of using those specific arrays? It would help, otherwise it looks like memorize the solution trying understand the meaning of arrays used
Great video and excellent explanation. I have tried it doing in O(col) space and was able to that. Can someone help me in finding the coordinates of the rectangle that are upper-left and bottom-right coordinates of an optimal rectangle?
We can even remove the last outer for loop. While calculating dpr itself, we can fit in the calculation of maxArea. Here is my java version. public int maximalRectangle(char[][] M) { if(M.length == 0) return 0; int rows = M.length, cols = M[0].length, maxArea = 0; int[][] dph = new int[rows + 1][cols], dpl = new int[rows + 1][cols], dpr = new int[rows + 1][cols]; for(int i = 0; i < rows + 1; i++) { for(int j = 0; j < cols; j++) dpr[i][j] = cols - 1; }
for(int r = 1; r < rows + 1; r++) { int lb = 0, rb = cols - 1; for(int c = 0; c < cols; c++) { if(M[r - 1][c] == '1') { dph[r][c] = dph[r - 1][c] + 1; dpl[r][c] = Math.max(lb, dpl[r - 1][c]); } else lb = c + 1; }
for(int c = cols - 1; c >= 0; c--) { if(M[r - 1][c] == '1') dpr[r][c] = Math.min(rb, dpr[r - 1][c]); else rb = c - 1;
// calculate maxArea here itself instead of another outer for loop if(M[r - 1][c] == '1') maxArea = Math.max(maxArea, (dpr[r][c] - dpl[r][c] + 1) * dph[r][c]); } }
@@KnapsackLabs ok! No problem! I have written the brute force solution in c++, which has O(N^6) Also, I have written the O(N^5) solution, using prefixsum array, and the O(N^4) solution , using prefixsum2Darray. Could post the solutions , if you wouldn’t mind.. ;) ( working some hours on this problem.... ;) )
I mean to say that if there is a rectangle that is taller than the lb, we have to use that bound because the taller rectangle could have a left bound farther to the right. We have to be conservative and take the leftbound which lies farthest to the right. This "conservative taking rightmost leftbound" is what I meant by more restrictive. Hope this helps!
For someone who is wondering what he means by the " more restrictive part" : (Read Along)
Let us say we have a row, as below and we are at the arrow mark downward(denoted by a V)
V
0 1 1 1 0
Now let us say the row above this is
0 0 1 1 0
So together let us say we have
V
1 0 0 1 1 0
2 0 1 1 1 0
Just reminding you that we need to calculate the value of the second row 4th element
If we talk about the second row 'lb' will hold the value 1, which denotes that the line of ones stretches from the 4th element to the first element in this row.
So the left bound is 1
But, if we have a row above it(row 1) such that the length of the rows of one is less that row 2
the rectangle will have to be of that smaller length.
This basically is the common area that we are taking. Read the above line again and you will get it!
Now we simply take the max because we want the rightmost bound on lb.
Hope this helps. If anyone still has a doubt feel free to ask!!!!
Great explanation by the way!!
It still doesn't make sense to me.
Suppose we have this:
0 0 0 1 0
0 1 1 1 0
And we are on 2nd row and 4th element. According to the algo, the lb of this will be 4 since the width of the upper two rectangle is just 1. So effective we will have a reactangle of size 2x1 which has area 2. But there is a larger reactangle possible from the second row with 3 1s. What is wrong here?
What i mean is, when we calculate the area of a reactangle using dph, dpl, dpr for some particular cell i,j in the grid, what does this tell us? The maximum area up until this cell? If so, then why do we need a right bound as that will go past that cell?
I've been watching your videos to help with my interview prep and they have been super helpful so far! I especially like how you write 1-2 lines of code then explain it which is well-suited for the interview process. Moreover, I appreciate have well-articulated your explanations are.
I was wondering which tools do you use to do the transitions when refactoring and highlighting certain parts of your code? And the tools for the diagrams you use?
This took a few watchthroughs to understand, it's a hard one. Thanks for this
Thanks for your clear explanation ! What is your strategy to come up with the DP table design in the first place? I was asked this in an initial screening interview and thrown off guard.
Great explanation!!
Why do we need to find the left and the right bound? Why can't we just keep a running max of the area of the largest reactangle with its bottom right corner at i,j ? Similar to the leetcode question max square (see ericchto's video for this)
very helpful to understand the complicated DP solution, thanks!
How one comes to the idea of using those specific arrays? It would help, otherwise it looks like memorize the solution trying understand the meaning of arrays used
solution is fine, but how to intuit this solution is missing. maybe its so complex it cannot be done. im not sure.
Great video and excellent explanation. I have tried it doing in O(col) space and was able to that. Can someone help me in finding the coordinates of the rectangle that are upper-left and bottom-right coordinates of an optimal rectangle?
We can even remove the last outer for loop. While calculating dpr itself, we can fit in the calculation of maxArea. Here is my java version.
public int maximalRectangle(char[][] M) {
if(M.length == 0) return 0;
int rows = M.length, cols = M[0].length, maxArea = 0;
int[][] dph = new int[rows + 1][cols], dpl = new int[rows + 1][cols], dpr = new int[rows + 1][cols];
for(int i = 0; i < rows + 1; i++) {
for(int j = 0; j < cols; j++) dpr[i][j] = cols - 1;
}
for(int r = 1; r < rows + 1; r++) {
int lb = 0, rb = cols - 1;
for(int c = 0; c < cols; c++) {
if(M[r - 1][c] == '1') {
dph[r][c] = dph[r - 1][c] + 1;
dpl[r][c] = Math.max(lb, dpl[r - 1][c]);
} else lb = c + 1;
}
for(int c = cols - 1; c >= 0; c--) {
if(M[r - 1][c] == '1') dpr[r][c] = Math.min(rb, dpr[r - 1][c]);
else rb = c - 1;
// calculate maxArea here itself instead of another outer for loop
if(M[r - 1][c] == '1') maxArea = Math.max(maxArea, (dpr[r][c] - dpl[r][c] + 1) * dph[r][c]);
}
}
return maxArea;
}
Is there a source code for brute force solution in c++? Thank you!
Unfortunately there isn't sorry!
@@KnapsackLabs ok! No problem! I have written the brute force solution in c++, which has O(N^6)
Also, I have written the O(N^5) solution, using prefixsum array, and the O(N^4) solution , using prefixsum2Darray. Could post the solutions , if you wouldn’t mind.. ;)
( working some hours on this problem.... ;) )
Yeah go for it!
github.com/bettypan-epanomi/max-rectanglular-of-1s-in-2darray/blob/main/https:/github.com/bettypan-epanomi/max-rectanglular-of-1s-in-2darray%20O(N%5E5)%20prefixsumarray
At 16.05, what do you mean by 'more restrictive'?
I mean to say that if there is a rectangle that is taller than the lb, we have to use that bound because the taller rectangle could have a left bound farther to the right. We have to be conservative and take the leftbound which lies farthest to the right. This "conservative taking rightmost leftbound" is what I meant by more restrictive. Hope this helps!
@@KnapsackLabs Thankyou for the fast reply. And the video was also very helpful.
If you're asked this question, probably they don't want to hire you =)