3
$\begingroup$

This is a computer science riddle with a really beautiful answer!

You are given as input an array of integers, representing a city skyline. Your goal is to find the rectangle of maximum area within this rectangle. For example:

arr = [1, 2, 3, 5, 1, 3]
   #
   #
  ## #
 ### #
######

In the example above, the answer would be 6, since you can create a rectangle of size 6 either with towers at index [1, 2, 3] (going horizontally), or [2, 3] (going vertically).

There is a twist however! In computer science, there is a data structure called the Fischer-Heun structure. You can read more about it here: http://web.stanford.edu/class/cs166/lectures/00/Small00.pdf

What you need to know for this riddle is that the structure can preprocess an array in time O(n), and then can answer queries, called minimum-range queries, in time O(1). A minimum range query allows you to get the index of the minimum value in a range of numbers. For example:

arr = [1, 2, 3, 5, 1, 3]
mrq = MRQ(arr) # happens in O(n), where n is len(arr)

mrq.minimum(2, 3) # returns 2, since the index of the minimum value in this range, 3, is 2.
mrq.minimum(1, 5) # returns 4. Since this index of the minimum value, 1 is 4.

Puzzle: Solve the maximum rectangle inscribed in skyline problem in O(n) time, using the minimum range query structure. I'll give some starter code to help out:

def recursive_helper(arr, mrq, i, j):
  ...

def minimum_rectangle_in_skyline(arr):
  mrq = MRQ(arr) # already takes O(n) time
  return recursive_helper(arr, mrq, 0, len(arr))
$\endgroup$
1
  • 4
    $\begingroup$ It seems that sometimes you say "minimum rectangle" when you mean "maximum"? $\endgroup$
    – A. Rex
    Feb 12, 2022 at 22:23

2 Answers 2

4
$\begingroup$

Here is an example skyline:

 #  ##
 ## ###
 ######
 ######

Now, the minimum element can either be or not be in the maximal rectangle.

If the minimum element is included in the maximal rectangle, we know the exact shape of the rectangle:

 #  ##
 ## ###
 XXXXXX
 XXXXXX

But, if the minimum element is not included, then we know that the maximal rectangle must be in the left or right half of the skyline, divided by the minimal element.

 A  BB
 AA BBB
 AA#BBB
 AA#BBB

We can use recursion to check how big the maximum rectangle is for A and B.

Here is the python code (doesn't include the Fischer-Heun structure):

def recursive_helper(arr, mrq, i, j):
  if not arr[i:j]:
    return 0
  min_i = mrq(i,j)
  min_v = arr[min_i]
  return max(min_v*(j-i),recursive_helper(arr,mrq,i,min_i),recursive_helper(arr,mrq,min_i+1,j))

def minimum_rectangle_in_skyline(arr):
  mrq = MRQ(arr) # already takes O(n) time
  return recursive_helper(arr, mrq, 0, len(arr))

Try it online!

Since we call the function recursive_helper 2n+1 times, and all the operations are O(1), our resulting time complexity is O(n). Without the Fischer-Heun structure, the time complexity of this algorithm would be O(nlogn) avarage and O(n^2) worst case.

$\endgroup$
4
  • 1
    $\begingroup$ Looks like a good write-up! Regarding the final sentence, do you just mean using a naïve implementation of the min-range query structure? The question can be solved in a different way, without the min-range concept entirely. $\endgroup$
    – A. Rex
    Feb 12, 2022 at 22:23
  • $\begingroup$ I second A. Rex. You can get the answer in O(n) time without the Fischer-Heun strucuture, but using a stack. The method is probaby similar to what is done to build the F-H structure. $\endgroup$
    – Florian F
    Feb 13, 2022 at 0:20
  • $\begingroup$ @A.Rex Yes, if instead we did a simple linear search to find the minimum $\endgroup$
    – AnttiP
    Feb 13, 2022 at 6:53
  • $\begingroup$ I like the MRQ answer more though :) $\endgroup$
    – weissguy
    Feb 13, 2022 at 22:10
2
$\begingroup$

Just for completeness, I've decided to include the stack based method (that weissguy and Florian F might have been referring to). This doesn't use the Fischer-Heun structure, but is still O(n)

Let's start again from the example skyline

 #  ##
 ## ###
 ######
 ######

Now, instead of recursing, we will walk the skyline from left to right. We also keep track of potential rectangles.

 #  ##
 ## ###
 ######
 ######
 ^

At this step, the maximum potential rectangle looks like this:

 AAAAAA
 AAAAAA
 AAAAAA
 AAAAAA
 ^

This obviously isn't the answer here, but it could be for a very dense and uniform skyline. We keep track of this rectangle.

 #  ##
 ## ###
 ######
 ######
  ^

Now we know for sure that this rectangle isn't possible. We will first truncate the rectangle:

 A  ##
 A# ###
 A#####
 A#####
  ^

and then we'll create an updated rectangle guess:

 #  ##
 BBBBBB
 BBBBBB
 BBBBBB
  ^

Then we move and repeat:

 #  ##
 ## ###
 ######
 ######
   ^

 #  ##
 BB ###
 BB####
 BB####
   ^

 #  ##
 ## ###
 CCCCCC
 CCCCCC
   ^

Next turn we don't have to truncate or update any rectangles, but we will have to add a new one:

 #  DDD
 ## DDD
 ###DDD
 ###DDD
    ^

Next turn, nothing happens (rect D is still a possibility)

 #  ##
 ## ###
 ######
 ######
     ^

Finally, at the last iteration:

 #  DD
 ## DD#
 ###DD#
 ###DD#
      ^

 #  ##
 ## EEE
 ###EEE
 ###EEE
      ^

After the final step every rectangle that remains is valid. In our case the biggest rectangle was C, so that is our answer.

Now, to store the potential rectangles we can use a stack, and store the height and the starting index of the rectangle. We are able to maintain the stack in height order (highest at the top) by removing the potential rectangles whose area we already know for sure. We only have to store a running maximum of the areas, and not the finished rectangles themselves.

Here is the python code:

def maximum_rect(arr):
  ans = 0
  stack = [(0,0)]
  for i,h in enumerate(arr+[0]):
    if stack[-1][1] < h:
      # Add new rectangles
      stack.append((i,h))
    while stack[-1][1] > h:
      # Truncate rectangles
      oi,oh = stack.pop()
      area = (i-oi)*oh
      ans = max(ans, area)
      # Add updated rectangles
      if stack[-1][1] < h:
        stack.append((oi,h))
  return ans

Try it online!

Since at every step we add at most 2 elements to the stack, and all other operations are O(1), the resulting algorithm is O(n)

$\endgroup$
1
  • $\begingroup$ That was pretty much what I did, with a bit of optimization. It was java but I ported it to python for comparison. Try it out. tio.run/… $\endgroup$
    – Florian F
    Feb 13, 2022 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.