2

I'm trying to solve the Largest Rectangle problem on HackerRank (https://www.hackerrank.com/challenges/largest-rectangle/problem) in python.

There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by h[i]. If you join k adjacent buildings, they will form a solid rectangle of area k * min(h[i], h[i + 1], ..., h[i + k - 1]).

Example

h = [3, 2, 3]

A rectangle of height h = 2 and length k = 3 can be constructed within the boundaries. The area formed is h * k = 2 * 3 = 6.

I got a suboptimal solution with the following code:

def area(h, i_start, k):
    return k*min(h[i_start:i_start+k])

def largestRectangle(h):
    largestArea = 0
    for i_start in range(len(h)):
        for k in range(1,len(h)-i_start+1):
            thisArea = area(h, i_start, k)
            if thisArea > largestArea:
                largestArea = thisArea
    return largestArea

While this works on many of the smaller test cases, it times out on the larger ones; I believe it's O(n^2) where n is the length of h.

I'd like to get a faster version, but I don't see how to avoid checking all widths k. Indeed, if after a certain point, the h's decline only very slightly, we'd want to make the rectangle as wide as possible, but if the decline is faster, then we should not widen the rectangle. Does anyone have a possible hint?

anatolyg
  • 26,506
  • 9
  • 60
  • 134
Philip Egger
  • 326
  • 1
  • 11
  • 1
    You can try divide and conquer for an O(n) solution: The largest rectangle it either the area under the lowest point or (recursion) the largest rectangle to either side of it. – fafl Jul 29 '21 at 13:43
  • This worked, thanks so much! If you post it as an answer, I'll gladly accept it. – Philip Egger Jul 29 '21 at 14:34

0 Answers0