Delete This!

This problem asks to find the enclosing rectangle such that the number of moves required to ensure an exact subset of items is within the bounds.

Iterating over all rectangles is too large, since the grid 10k square (convenient size for ensuring n^2 is too slow...). However, we know that we can greedily shrink any optimal solution to the nearest items inside the boundary (think a rectangular convex hull....thing). This means that any optimal solution has a equivalent solution which has some item lying just on each side of the bounding box.

This means we can find an optimal solution by iterating over all n-choose-4 boxes and then evaluating how many moves we need to make.

The issue here is that the naive evaluation method (iterating over all items and checking them against box bounds) is another n, and O(n^5) is too large (again....how convenient?). So that means we need an amortized sublinear time to calculate the number of moves for each box. This is relatively straightforward if we iterate over the n-choose-4 boxes in the right order.

• For the item defining the "top" or "bottom" of the bounding box, go in decreasing Y direction
• For the item defining the "left" and "right" of the bounding box, go in increasing X direction

Each time you move the bottom or right hand side, you include one more box. If this is a "inside" box, you decrement the count by 1, and if it's an "oustide" box, you increment it. Note you have to consider ALL boxes with the same coordinate, so perhaps storing that in a hash map might be a good idea to still get constant time. top or left...and thus have to "reset" the right or bottom, just recompute the whole thing.

One can cut the time by 4x by ignoring "invalid" boxes where right/left or top/bottom are backwards.