Largest Rectangle — HackerRank

Python Stacks Application Example

Question:

Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.

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

Example:

INPUT:
5          
1 2 3 4 5  ----------> input given : h=[1,2,3,4,5] , n=5

OUTPUT:
9 

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

Solution:

import math
import os
import random
import re
import sys

def largestRectangle(heights):
    area = 0
    stack  = [] #-------------------------> stack of tuples (i,h)
    for i,h in enumerate(heights):
        start = i
        while stack!=[] and stack[-1][1] > h:
            index,height=stack.pop()
            area=max(area, (i-index)*height)
            start = index
        stack.append((start, h))

    for i,h in stack:
        area = max(area,h*(len(heights)-i))

    return area

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input().strip())
    h = list(map(int, input().rstrip().split()))
    result = largestRectangle(h)
    fptr.write(str(result) + '\n')
    fptr.close()

Thanks for reading. Leave your thoughts in the comments :)