Great explanation. I've been struggling with this one. All over the internet people just plonk their code down without explanation, but you explain it so simply.
What exactly did he explain? He has an algorithm and he is walking through the algorithm... Nothing more than that. No word on HOW he came up with the algorithm or what is the intuition behind this...
Each row adds to values for histogram bars unless the cell value is 0 .. (i.e. bar is gone) and so at each row/level we check out maximum area under histogram (above the row)..which is the max rectangle.
thnaks a lot tushar . i almost learnt all dp algorithm u provided. plz carry on ur great effort. and provide us more tutorial . I have learnt dynamic programmong from ur tutorial . i am indebted to you
Only a trivial personal thought for why the "histogram" strategy works: a rectangle must have its bottom width land on a row. Here, we are simulating through all the rows for to get the bottom width to make the rectangle the maximum.
+Tushar Roy At time @5:44 u said that the Maximum Size Rectangle containing 1's is that (located at bottom down). How did u find that that is the box containing max 1's .Obv by luking at box v know that since max size is 8 and this box size is also 8 ,v can say that yes this box is the one , but how will a computer do it ? V know that the max size is 8, how to find the position of that box ?
@Exodus .. The histogram is formed taking into account the previous rows. The height of any bar in the histogram is dependent on the previous row . If you look closely if (i, j) == 0 then our histogram height there is 0. But if (i,j)==1 then histogram height is height(i-1, j) + 1. Formally Say, h(i, j) = height of histogram bar at i, j then if (i, j) == 1: ....h(i, j) = h(i-1, j) + 1 else: ...h(i, j) = 0 Hope this helps
for a rectangle we need two things, length and breadth, as the width is maintained by the array by summing up, then we just have to the appropriate length for given possible width so that we can decide our rectangle. So, with the help of histogram area here we are just deciding the best possible length we can have for a rectangle.
Hi Tushar..first of all thanks a lot for all your efforts..I have learnt a lot from you. Can we use and expand the same procedure above to find the largest subcube in a NxNxN cube cosisting of 1x1x1 subcubes with values either 0 or 1. like adding a new dimension to it. If possible can you please suggest the way forward
+Tushar Roy You write this algorithm has O(rows * columns) complexity. This suggests that finding rectangle in histogram is solvable in O(1) - this feels very wrong.
1] 100 MAX is 1 2] 010 MAX is 1 3] 120 MAX is 2 When a row has a zero in it, it overrides the value in that slot, if that didn't happen then row three would have returned 220, which as we know is incorrect. Hope that helps, I don't think he explicitly mentions that behavior in the video, but it's there
Just store the row no. when u update the max_area first time and last time. For column no. get the indexes of the array when u calculate its area in histogram.
***** so in your video the last histogram values are 0 0 3 4 2 4 According to my suggestion length of longest consecutive array is 4 min value in the consecutive array is 2 highest value is 4 area = max ((min * length of longest consecutive array), (highestValue in the array)) area = max((2*4),4) area = max(8,4) area = 8 Time complexity O(length of the histogram array) Another example histogram array values 0 6 0 2 1 0 length of longest consecutive array is 2 min value in the consecutive array is 1 highest value is 6 area = max ((min * length of longest consecutive array), (highestValue in the array)) area = max((1*2),6) area = max(2,6) area = 6 Correct me if my solution seems wrong.
***** Makes sense I did realize that once I posted the comment. Although we could still use the formula for each consecutive array and compare the current max to the previous max .. and at the end of the array we can get the max of the entire array. 9,0,3,3,3,3,,0,1,1,1,1,1,1,1,1 Set arrayMax = 0 First Check max(9,0) arrayMax = 9; Second Check max(9,12) arrayMax=12; Third Check max(12,8) arrayMax =12 end of the array return arrayMax; So my formula would change to arrayMax = max ((min value in consecutive array * length of consecutive array), arrayMax);
***** Agreed did not consider this use case. Yeah my solution would return 5 in this case . But the max area should be 6. Is that correct? I just went down the rabbit hole trying to come up with a solution to it. Thanks for all the use cases.
Is it possible to adapt this algorithm to find out biggests border with 1s ? (which means the inside of the subrectangle need not be 1) ? Great video btw!
In your videos there is one issue, You should first explain the approach on the basis of test cases and slowly move towards building the algorithm. I meant to say that how we can approach a new problem that should be discussed .The solutions to problem can be found anywhere but only to understand the journey which lead to that solution we watch the videos. Thanks
+Tushar Roy, this method works for all examples? Suppose the 5x5 2D matrix is 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 According to your method, the answer 4. Whereas the answer should be 6 (or 8 if you consider the vertical rectangle) Please help!
ya this algo will work for all examples, for your example too for 1st row 1 0 0 0 1 max rectangle is 1 for 2nd row 0 1 1 1 0 max rectangle is 3 i.e. largest rectangle in histogram made by this array for 3rd row 1 2 2 2 0 max rectangle is 6 for 4th row 0 0 3 3 0 max rectangle is 6 for 5th row 1 1 4 4 0 max rectangle is 8 hence your answer i hope u got it 1 1 4 4 0 all indicates the height of histogram at each index of width 1 unit and u have to find the max area in each histogram and compare with the last one
Oh. For the third row, you do not consider that 1 while taking the max rectangle? If you take that 1, the max rectangle will be 4. So will have to apply some algorithm to choose the elements that form the max rectangle instead of considering all the non zero elements. Thanks for your help!
You do consider that 1. He probably overlooked it. Row 3 = 00331. However this doesn't affect the maxArea. since max rectangle at this point will be: 111 111
lets take example of 1,0,1,0.. and when we run following line after reaching last 0 (i==3) else { area = arr[top] * i; }...it will give 1*3 = 3 (where arr[top] =1 & i =3)
A noob programmer like me would take these few variable. startI , startJ and run a loop from startI=0 till less than maxArea startJ=0 till less than maxArea Search if all values in this range are 1's. If you find a 0. Just shift this whole Window accordingly till you find the rectangle. Though this probably isnt the best way to do it, but I'm a noob and that's how I did it.
Thank you for everything! You are amazing! However, I believe this theory does not work for the following example (the number of lines is n=5 and the number of columns is m=5): 5 5 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1
First of all, thanks for your videos, you've created a very wide collection :) Either you are missing a step or I'm missing something. Here's an example: I isolated the problem to a very simple test case. Imagine that your matrix is a very simple one 10 01 your first histogram will be: 10 max area is 1 using your accumulation method, the second histogram will become 11 the max area is 2 which brings us to final answer of 2, which is obviously not a valid answer. Am I missing something here ? Any feedback is welcome :)
2020 - still the best explanation IMHO
2021 - still the best explanation IMVHO
Great explanation. I've been struggling with this one. All over the internet people just plonk their code down without explanation, but you explain it so simply.
What exactly did he explain? He has an algorithm and he is walking through the algorithm... Nothing more than that. No word on HOW he came up with the algorithm or what is the intuition behind this...
@@nikostrongioglou9941 exactly. Nothing on thought process.
getting things very easily by listening to ur lectures... thank u :-)
Great explanation! You should write a book "cracking the code interview"
No bro! He should write the book "how to make the coding interview become a funny game". I feel really comfortable about his explain
You can always explain complex algorithm in a simple way! love your video!
U are always saviour for any tough question. Thanks for such simple explanation.
Each row adds to values for histogram bars unless the cell value is 0 .. (i.e. bar is gone)
and so at each row/level we check out maximum area under histogram (above the row)..which is the max rectangle.
ya your explanations are simple , so easy to understand.. Thanks!!
why are we using histogram ?
@@samarthsharma9019 For that answer, you have to look at this problem: "Largest Rectangular area in Histogram"
where were you all my life. Been struggling way too hard with this problem yet it's so simple.
thnaks a lot tushar . i almost learnt all dp algorithm u provided. plz carry on ur great effort. and provide us more tutorial . I have learnt dynamic programmong from ur tutorial . i am indebted to you
What I like about you, is you save a lot of time, thanks man
an intuition to the approach would have been amazing. but great explanation!
can we get an explanation on why this approach works?
@@Bdjdiwhbkdk Thanks it really clear things up
Beautifully explained
Really best explanation
How would you modify this algorithm to return all the coordinates of the largest rectangle, or a specific corner & the width and height?
we need 3 things to get co-ordinates length breadth and lower left vertex: i think now you can find it anyways Im not going to type all of that
Only a trivial personal thought for why the "histogram" strategy works: a rectangle must have its bottom width land on a row. Here, we are simulating through all the rows for to get the bottom width to make the rectangle the maximum.
Every time I see his videos, I feel like its raining in the background
or raining from ground hahahahahhah
Thanks for short and clear explanation!
Lovely tutorials, Thanks alot Tushar!
Learning so much from you!
so fast yet so clear. great explanation!
+Tushar Roy
At time @5:44 u said that the Maximum Size Rectangle containing 1's is that (located at bottom down). How did u find that that is the box containing max 1's .Obv by luking at box v know that since max size is 8 and this box size is also 8 ,v can say that yes this box is the one , but how will a computer do it ?
V know that the max size is 8, how to find the position of that box ?
+Tushar Roy
Ok thnx
is this dynamic programming solution? We are not using solution to subproblems to get the final solution.
Great question. Yes, we are. In order to solve for the input that we are given, we need to build the solution up row by row
@Exodus .. The histogram is formed taking into account the previous rows. The height of any bar in the histogram is dependent on the previous row . If you look closely if (i, j) == 0 then our histogram height there is 0. But if (i,j)==1 then histogram height is height(i-1, j) + 1.
Formally
Say, h(i, j) = height of histogram bar at i, j
then
if (i, j) == 1:
....h(i, j) = h(i-1, j) + 1
else:
...h(i, j) = 0
Hope this helps
I think it can be solved in O(1) space complexity , if you use 1st row or 1st column instead of extra array . Since you have no further use of it
I think that what you are proposing will still be 0(n), where n is the width of the original array.
Agree with Billy Yang.
Also, finding the largest histogram function itself might take a space of O(col/rows).
Why can't I like these videos more than once!!
This is part of product design of 'TH-cam'.
Feel free to contact youtube devs
You Nicely build upon algorithm which u alrdy taught us!! Thanks Tushar!!
Hi Tushar,
You explain every problem very well, but I dont understand why this histogram logic works here. Please explain..Thanks
for a rectangle we need two things, length and breadth, as the width is maintained by the array by summing up, then we just have to the appropriate length for given possible width so that we can decide our rectangle.
So, with the help of histogram area here we are just deciding the best possible length we can have for a rectangle.
Could you explain how to calculate max histogram area without using the library function?
Keeping the smallest of a continuous subset of non zero values
You can calculate using stack
Please can you explain why this approach is working? what is the intuition behind it?
Hi Tushar..first of all thanks a lot for all your efforts..I have learnt a lot from you.
Can we use and expand the same procedure above to find the largest subcube in a NxNxN cube cosisting of 1x1x1 subcubes with values either 0 or 1. like adding a new dimension to it. If possible can you please suggest the way forward
Really you are amazing .. One of the best
Although you explain things pretty easily but they are to be memorized if we go by your way.
You are awesome. Your videos helped me a lot . Thanks man :)
Thank you Gautam gambhir
I would have really appreciated if you could have spent 1 min on code implementation at very high top level. +1 for your efforts on explanation.
Great explanation
Thanks sir, this video made this question very easy .
+Tushar Roy
You write this algorithm has O(rows * columns) complexity. This suggests that finding rectangle in histogram is solvable in O(1) - this feels very wrong.
sorry, You are right.
Mateusz Lewicki I'm concerned about it too..
@Tushar any idea how to compute the largest cross please?
nice video but how is an area of 5 a rectangle?
Good one Tushar!!!
Hi Tushar...
I have one question: why the algorithm of maximum size square of all 1's will not work here?
amazing explanation! Thank you!
Looking at leetcode - Would temp[j]++ work instead of temp[j] += input[i][j]; on line 40 ?
Hello Tushar awesome explanation
can you pls advice book/wiki for this algorithm.
I am looking for explanation how to come to the described algorithm, but instead see what to do without explaining why
Thankyou .you made DP so easy .
Do you have any videos Maximum Distance Matrices (MDS)? If not, could you do a quick one? Thx
You are a gem, mate.
nice explanation
Nice explanation, thank you : )
how do you find the largest multiplication value in each row?
Extremely helpful!
with the following case
100
010
110
if we use the largest rectangle method wouldn't his case result be 4?(2 in the first col and 2 in the second col)
but the actual result is 2
1] 100 MAX is 1
2] 010 MAX is 1
3] 120 MAX is 2
When a row has a zero in it, it overrides the value in that slot, if that didn't happen then row three would have returned 220, which as we know is incorrect. Hope that helps, I don't think he explicitly mentions that behavior in the video, but it's there
why do we add from the top in case of 1. Can anyone please explain?
Thanks for such a good video..
You made it really easy to understand, thank you
great sir great thank you
good explanation, thanks !!
what is the Intuition behind this working?
Is there a way to find indexes of largest rectangle?
Just store the row no. when u update the max_area first time and last time. For column no. get the indexes of the array when u calculate its area in histogram.
Another way to find max area would be
area = max ((min * length of longest consecutive array), (highestValue in the array))
***** so in your video the last histogram values are 0 0 3 4 2 4
According to my suggestion
length of longest consecutive array is 4
min value in the consecutive array is 2
highest value is 4
area = max ((min * length of longest consecutive array), (highestValue in the array))
area = max((2*4),4)
area = max(8,4)
area = 8
Time complexity O(length of the histogram array)
Another example
histogram array values 0 6 0 2 1 0
length of longest consecutive array is 2
min value in the consecutive array is 1
highest value is 6
area = max ((min * length of longest consecutive array), (highestValue in the array))
area = max((1*2),6)
area = max(2,6)
area = 6
Correct me if my solution seems wrong.
***** Makes sense I did realize that once I posted the comment. Although we could still use the formula for each consecutive array and compare the current max to the previous max .. and at the end of the array we can get the max of the entire array.
9,0,3,3,3,3,,0,1,1,1,1,1,1,1,1
Set arrayMax = 0
First Check
max(9,0)
arrayMax = 9;
Second Check
max(9,12)
arrayMax=12;
Third Check
max(12,8)
arrayMax =12
end of the array return arrayMax;
So my formula would change to
arrayMax = max ((min value in consecutive array * length of consecutive array), arrayMax);
***** Agreed did not consider this use case. Yeah my solution would return 5 in this case . But the max area should be 6. Is that correct? I just went down the rabbit hole trying to come up with a solution to it. Thanks for all the use cases.
hey it is not a dp approach so Y ur title include dp
why 8? i cant undrestand:(
in which video did you discuss maximum size square in matrix?
***** thanks
thats really cool .....nice explination.
how to solve problem when we want found maximum rectangle with- all of 0s
convert 0 to 1 and 1 to 0 in the array and then do the same process on the new matrix.
Whats the intuition behind this?
tushar, you are my hero
Is it possible to adapt this algorithm to find out biggests border with 1s ? (which means the inside of the subrectangle need not be 1) ? Great video btw!
Bro, in samsung they asked me this problem to find out biggests border with 1s and I could not make any progress.
In your videos there is one issue, You should first explain the approach on the basis of test cases and slowly move towards building the algorithm. I meant to say that how we can approach a new problem that should be discussed .The solutions to problem can be found anywhere but only to understand the journey which lead to that solution we watch the videos. Thanks
what if rows could be changing the places ? hm....
Nice video. And recthaangle. Haha 😀
Thanks man!
+Tushar Roy, this method works for all examples?
Suppose the 5x5 2D matrix is
1 0 0 0 1
0 1 1 1 0
1 1 1 1 0
0 0 1 1 1
1 1 1 1 0
According to your method, the answer 4. Whereas the answer should be 6 (or 8 if you consider the vertical rectangle)
Please help!
ya this algo will work for all examples, for your example too
for 1st row 1 0 0 0 1 max rectangle is 1
for 2nd row 0 1 1 1 0 max rectangle is 3 i.e. largest rectangle in histogram made by this array
for 3rd row 1 2 2 2 0 max rectangle is 6
for 4th row 0 0 3 3 0 max rectangle is 6
for 5th row 1 1 4 4 0 max rectangle is 8
hence your answer i hope u got it 1 1 4 4 0 all indicates the height of histogram at each index of width 1 unit and u have to find the max area in each histogram and compare with the last one
Oh. For the third row, you do not consider that 1 while taking the max rectangle? If you take that 1, the max rectangle will be 4. So will have to apply some algorithm to choose the elements that form the max rectangle instead of considering all the non zero elements. Thanks for your help!
You do consider that 1. He probably overlooked it. Row 3 = 00331. However this doesn't affect the maxArea.
since max rectangle at this point will be:
111
111
It not working for all case
Ye sahi banda h!
Like comment if your think the same!
Maybe a 3D histogram?
Max sum😍😍😍😍😍
Hi Tushar...Thanks for helpful video..1 query - how to handle non contiguous array like 0,0,2,0,0,2.
+Sheetal according to your code, its giving area = 0...please correct if something is missing
lets take example of 1,0,1,0.. and when we run following line after reaching last 0 (i==3) else
{
area = arr[top] * i;
}...it will give 1*3 = 3 (where arr[top] =1 & i =3)
Thank you sir
@2:44, the value should be 1
***** sorry my bad. I didn't listen to it clearly.
Btw, great set of videos. Keep up the good work.
anyone can tell me how to find starting index of rectangle in this question
A noob programmer like me would take these few variable.
startI , startJ and run a loop from
startI=0 till less than maxArea
startJ=0 till less than maxArea
Search if all values in this range are 1's. If you find a 0. Just shift this whole Window accordingly till you find the rectangle.
Though this probably isnt the best way to do it, but I'm a noob and that's how I did it.
I think time complexity is O(RC^2)
how we can do it for parallelogram?
how do you represent parallelogram in a data structure?
Awesome !
Better to explain the logics first before throwing in the solution.
Thank you for everything! You are amazing!
However, I believe this theory does not work for the following example (the number of lines is n=5 and the number of columns is m=5):
5 5
0 1 0 1 1
0 1 1 1 1
0 1 0 1 1
0 1 1 1 1
0 1 1 1 1
it will work.. answer will be 10
just Awsome
mind = blown!
First of all, thanks for your videos, you've created a very wide collection :)
Either you are missing a step or I'm missing something. Here's an example:
I isolated the problem to a very simple test case.
Imagine that your matrix is a very simple one
10
01
your first histogram will be:
10
max area is 1
using your accumulation method, the second histogram will become
11
the max area is 2
which brings us to final answer of 2, which is obviously not a valid answer.
Am I missing something here ? Any feedback is welcome :)
+Tushar Roy
Thanks, now it makes sense
:)
thanks :)
Thanks
Keep visiting again n again you fool 😠
This is wrong ! If we swap index 2,4 to 1,4 we ll still get same answer , but the matrix is not all made of 1's ..check at 5:53
You are GOD !
But how to calculate max histogram area.😂
Time Complexity should be O( rows * cols^2)
check the code here also if you want
cpincpp.blogspot.com/2020/09/maximal-rectangle-in-given-matrix-with.html
are you a robot
suppose my row value were 3 3 4 2 then max area acc to you would have been 8 but 9 is the max value.
+The rock
first check the histogram area calculation algorithm video,
then you will come to know every thing is proper.