Grand Temple Solution

#1

I’m not able to understand/ make the solution for this problem. Pls, help me with the same.

#2

Hey @shifali1998,
You are provided with the coordinated through which 2 rivers flow- one horizontally and the other one is flowing vertically. You have to build a temple provided the condition that the temple must be enclosed with a river on all 4 sides. You are supposed to find the max possible area for the temple.
For every possible area you must have a rectangle which is enclosed by different rivers on each side.

Sample Input

3
1 1
2 4
5 2

We have 3 points through which rivers flow horizontally as well as vertically.
For the 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. We also need to assume that the width of the river is 1 unit.
So, while calculating the area we need to ignore the area covered by river 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 to be (3,2), (3,4), (5,2), (5,4) after removal of the area covered by the river. Thus, giving the maximum area as 2 units.

According to the Question , you are basically given n*n matrix and some coordinates, whose entire horizontal row line as well as vertically column line should be considered as river line. You need to find the maximum area of land which is enclosed by rivers on all 4 sides.

You can implement the following approach:

  1. Make two arraylists:
    1.1. first: to store the x coordinates provided as input.
    1.2. second: to store all the y coordinates provided as input.
  2. Sort both the lists.
  3. Find the maximum difference between the adjacent elements of each vector as dx and dy.
  4. Print the Area by multiplying both the differences.

Note:
Observe the figure carefully, you have to subtract 1 from both dx and dy before multiplication.

Hope, this would help.

1 Like
#3

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.

1 Like