What is the approach to solve this problem

#1

i have understood the problem but i am not able to code the solution for it

#2

@jatin111 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.

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.

If you still has doubt, just lemme know else resolve it bro!

#3

can you explain this with an example

#4

@jatin111 In this question you are given that there are some watchtowers at different coordinates (x,y). Now 2 rivers flow horizontally and vertically and they intersect at this tower

grandtemple

Here you can see that there are 3 towers at (8,6), (3,8) and (11,2) and for each of them 2 rivers (1 horizontal and the other vertical and flowing and intersecting at the respective (x,y)).
Given this arrangement the rest of the space left in the grid(the white portion in image) is land.
Now the king wants to build a temple and he wants to do that on the largest area available. Now you are required to find out and print the area of the largest land which is available and in which the king can build a temple.

now you are supposed to find the max area, and for having an area you must have a rectangle for that you will need 4 points and for given test case we found that 2,2), (2,4), (5,2), (5,4) these are the 4 points which will give us the maximum area. There is one thing you need to keep in mind while calculating the area i.e. the area will be calculated from the edge next to the left edge, the edge above the bottom edge, the topmost edge and the rightmost edge, therefore for the region (2,2) , (2,4) , (5,2) , (5,4) the actual area will be considered from (3,2), (3,4), (5,2), (5,4) respectively.

Approach
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 -Xi-1) & ΔY = (Yi -Yi-1). Then the area will be (ΔY-1)*(ΔX-1).

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.

Now bro first try to study and code this approach.

#5

thanks bro for explaining it soo well