can’t able to understand what the question is saying
Can't able to understand this problem
Just imagine an n x m board of cells, and you are given some horizontal as well as some vertical lines that are colored black, rest of the cells remain white. You need to white the area of the rectangle which consists of only white cells and has maximum area.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
not able to understand this problem with the test cases given ,how 2 will be the largest area
We have to find the maximum area of land(so we exclude the rivers).
Clearly the maximum area would be between the intersection points of (2,4) and (5,2) for the given sample testcase.
Area = | 5 - 2 - 1 | * | 2 - 4 - 1| = 2 * 1 = 2
We implement the formula ,
Area = abs( y2 - y1 - 1) * abs( x2 - x1 - 1)//take abs as area cant be negative
We add an extra -1 in our calculation since we should consider the river area. If we simply implement (y2 - y1) or (x2 - x1) then we would end up counting 1 edge of the vertical river and 1 edge of the horizontal river. We should not include that area as the temple cannot be built over the river edge.
You can refer to the image below.
no test cases are passing
https://ide.codingblocks.com/s/238164 corrected code.
You have to maximise the area obtained between the rivers. Since the intersection points of rivers are provided to you as input , you need to find the largest consecutive gap between the x coordinates and y coordinates.
This problem falls under the Greedy Algorithms section. A very similar problem ( practically the same ) is covered in the Greedy Algorithms tutorial video as well.
You need to implement a greedy algorithm for this problem.
Take the x coordinates input in an array , say X .
Take the y coordinates input in an array , say Y .
We need to find the maximum area. We can obtain it by finding the largest gap in the x coordinates and multiplying with the largest gap in the y coordinates.
So just do that , find the maximum gap between consecutive x coordinates in the X array and do the same for Y.
Multiply these maximum gaps and you will have your maximum area.
Hint : Sorting might help.
This is a pretty simple problem. All we need to do is just store all the X and Y coordinates and then sort them. Then we will calculate maximum ΔX and ΔY where ΔX = (Xi -X(i-1)) & ΔY = (Yi -Y(i-1)).
Then the area will be (ΔY-1)*(ΔX-1)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.