The largest empty rectangle whose base is on the x axis

Question

Original issue: Issue 2

In a rectangular space with a height of 500 and a width of 10 ^ 5 we get N points.

We need to find the largest sub-rectangle, the base of which is on the x axis and does not contain any of the points in its own internal space (but can contain them along the edges).

I tried the O algorithm (width ^ 2):

#include <iostream> #include <algorithm> const int nWidth = 100000; const int nHeight = 500; int main(){ int *nMaxHeights = new int[nWidth]; std::fill (nMaxHeights, nMaxHeights+nWidth, nHeight); int N; std::cin >> N; for (int x,y,iii=0; iii < N; iii++){ std::cin >> x >> y; nMaxHeights[x] = std::min(y+1, nMaxHeights[x]); } int maxArea = 0; for (int jjj,iii=0; iii < nWidth; iii++){ for (jjj=iii; jjj < nWidth; jjj++){ if (nMaxHeights[jjj] < nMaxHeights[iii]) break; } maxArea = std::max((jjj-iii+1)*nMaxHeights[iii],maxArea); } std::cout << maxArea; return 0; } 

It works, but obviously gets a TLE (runtime limit exceeded).

How am I better?

Answer 1

An interesting problem. Thanks for pointing this out.

I used an algorithm that scales O(N) for a larger N (number of points) and a random distribution of points. The idea behind this: each rectangle will be bounded by some point (s).

• If there are more points for a single x value, only the one with the lowest y value is used.
• First check the extreme points of x; the rightmost and leftmost spanning rectangle respectively. limits.
• Then go to the rightmost point and try to build a rectangle, including it. There are two possibilities:
  • this point is on the horizontal edge: find its two neighborhoods on the left and on the right that have a lower y value and use them as points on the left or. right edge. If there is no left / right neighbor, use the end of the space.
  • This point is on the vertical edge: find the next left point, use the (y-) space limit as the horizontal edge.
• For each point, calculate the areas of the possible rectangles (two possibilities are higher), and if they are larger than the current largest area, update the largest area.

Here is an example implementation in python, http://pastebin.com/068ByYwh , but I'm not sure that it contains no errors ;-)

Answer 2

Imagine only one point. There are three possible rectangles: below the point, to the left of it and to the right of it.

Say now there are two points. Let's look at what's closer to the bottom. Again, there are three cases at this point. There is below the rectangle. There is a rectangle on the side opposite to another point. And there is a side with a different point, where there are more rectangles.

IOW, if you look at the points from bottom to top, then each point has a rectangle at the bottom, and this point divides the space into two vertical stripes, each of which has other points that also have rectangles under them and which further divide the space.

Thus, it would be wise to sort the points both by Y and by X (possibly by making them nodes of two sorted trees, sorted by Y (so you can move upwards by Y), and another, sorted by X (so you can move / look left / right)), which is N * log (N), and then recursively visit all points from bottom to top, appropriately dividing the space that looks like another N * log (N).