Largest Rectangle size after each query (Algorithm)

user_6354622 0
Viewed 77

I recently came across this algorithmic question in an interview. The question goes something like:

Initially there is a rectangle (starting at the origin (0,0) and ending at (n,m)) given. Then there are q queries like x=r or y=c which basically divides the initial rectangles into smaller rectangles. After each query, we have to return the largest rectangle size currently present.

See the diagram:

enter image description here

So, here we were initially given a rectangle from (0,0) to (6,6) [a square in fact!!]. Now after the 1st query (shown as dotted line above) x = 2, the largest rectangle size is 24. After the second query y = 1, the largest rectangle size is 20. And this is how it goes on and on.

My approach to solving this:

At every query, find:

  1. The largest interval on the x axis (maxX) [keep storing all the x = r values in a list]

  2. The largest interval on y axis (maxY) [keep storing all the y = c values in another list]

At every query, your answer is (maxX * maxY)

For finding 1 and 2, I will have to iterate through the whole list, which is not very efficient.

So, I have 2 questions:

Is my solution correct? If not, what is the correct approach to the problem. If yes, how can I optimise my solution?

rectangles sorting algorithm
2 Answers

It's correct but takes O(n) time per query.

You could, for each dimension, have one binary search tree (or other sorted container with O(log n) operations) for the coordinates (initially two) and one for the interval sizes. Then for each query in that dimension:

  1. Add the new coordinate to the coordinates.
  2. From its neighbors, compute the interval's old size and remove that from the sizes.
  3. Compute the two new intervals' sizes and add them to the sizes.
  4. The largest size is at the end of the sizes.

Would be O(log n) per query.

user_126710570

Yes, your algorithm is correct.

To optimize it, first of all, consider only one dimension, because the two dimensions in your geometry are fully orthogonal.

So, you need to have a data structure which holds a partitioning of an interval into sub-intervals, and supports fast application of these two operations:

  1. Split a given interval into two
  2. Find a largest interval

You can do that by using two sorted lists, one sorted by coordinate, and the other sorted by size. You should have pointers from one data structure to the other, and vice-versa.

To implement the "splitting" operation:

  1. Find the interval which you should split, using binary search in the coordinate-sorted list
  2. Remove the interval from both lists
  3. Add two smaller intervals to both lists
user_5098680
Related