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
+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.
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
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.
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
+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
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!
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.
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.
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
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 :)
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
![Burst Balloon Dynamic Programming[Leetcode]](http://i.ytimg.com/vi/IFNibRVgFBo/mqdefault.jpg)
![Burst Balloon Dynamic Programming[Leetcode]](/img/tr.png)
2020 - still the best explanation IMHO
2021 - still the best explanation IMVHO
@@hitesh3859 2024 - still the best explanation IMVHO
getting things very easily by listening to ur lectures... thank u :-)
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.
What I like about you, is you save a lot of time, thanks man
U are always saviour for any tough question. Thanks for such simple explanation.
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
Really best explanation
Beautifully explained
where were you all my life. Been struggling way too hard with this problem yet it's so simple.
Thanks for short and clear 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.
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
so fast yet so clear. great explanation!
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"
Really you are amazing .. One of the best
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
Lovely tutorials, Thanks alot Tushar!
Learning so much from you!
Good one Tushar!!!
You are awesome. Your videos helped me a lot . Thanks man :)
an intuition to the approach would have been amazing. but great explanation!
You Nicely build upon algorithm which u alrdy taught us!! Thanks Tushar!!
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 ?
+Tushar Roy
Ok thnx
Great explanation
amazing explanation! Thank you!
can we get an explanation on why this approach works?
@@Bdjdiwhbkdk Thanks it really clear things up
You are a gem, mate.
Please can you explain why this approach is working? what is the intuition behind it?
Every time I see his videos, I feel like its raining in the background
or raining from ground hahahahahhah
Thank you Gautam gambhir
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).
Hello Tushar awesome explanation
can you pls advice book/wiki for this algorithm.
Although you explain things pretty easily but they are to be memorized if we go by your way.
Nice explanation, thank you : )
Thanks sir, this video made this question very easy .
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
Thankyou .you made DP so easy .
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
Extremely helpful!
Thanks for such a good video..
+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..
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
You made it really easy to understand, thank you
nice explanation
good explanation, thanks !!
great sir great thank you
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.
@Tushar any idea how to compute the largest cross please?
nice video but how is an area of 5 a rectangle?
Looking at leetcode - Would temp[j]++ work instead of temp[j] += input[i][j]; on line 40 ?
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
tushar, you are my hero
what is the Intuition behind this working?
Do you have any videos Maximum Distance Matrices (MDS)? If not, could you do a quick one? Thx
thats really cool .....nice explination.
Max sum😍😍😍😍😍
Hi Tushar...
I have one question: why the algorithm of maximum size square of all 1's will not work here?
why do we add from the top in case of 1. Can anyone please explain?
Nice video. And recthaangle. Haha 😀
how do you find the largest multiplication value in each row?
I am looking for explanation how to come to the described algorithm, but instead see what to do without explaining why
in which video did you discuss maximum size square in matrix?
***** thanks
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
hey it is not a dp approach so Y ur title include dp
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.
Thanks man!
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.
+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
Whats the intuition behind this?
Thank you sir
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.
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.
what if rows could be changing the places ? hm....
why 8? i cant undrestand:(
how we can do it for parallelogram?
how do you represent parallelogram in a data structure?
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.
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)
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.
just Awsome
Awesome !
@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.
Maybe a 3D histogram?
It not working for all case
mind = blown!
thanks :)
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
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
Thanks
Keep visiting again n again you fool 😠
Lmao love your videos and your hair
Ye sahi banda h!
Like comment if your think the same!
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
:)
I think time complexity is O(RC^2)
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
But how to calculate max histogram area.😂
check the code here also if you want
cpincpp.blogspot.com/2020/09/maximal-rectangle-in-given-matrix-with.html
You are GOD !
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.
Time Complexity should be O( rows * cols^2)
are you a robot