• + 0 comments

    Brute force solution without stacks that passes some tests but only fails with time limit exceeded. So, I'd say logic is correct. This is O(N!) algorithm, it generates all the possible arrangements of size 1, size 2, .... size N. Absolutely not optimal but it uncovers the neccessary thought pattern to solve optimally.

    def largestRectangle(h): maxRectangleArea = float("-inf")

    size = 1
    while size <= len(h):
        for i in range(len(h)):
            minHeight = float("inf")
    
            if  i + size > len(h):
                break 
    
            for j in range(i,i+size):
                minHeight = min(minHeight, h[j])
            maxRectangleArea = max(maxRectangleArea, (minHeight * size))
        size += 1
    return maxRectangleArea