HackerRank ‘Largest Rectangle’ Solution

Short Problem Definition:

There are NN buildings in a certain two-dimensional landscape. Each building has a height given by hi,i∈[1,N]hi,i∈[1,N]. If you join KK adjacent buildings, they will form a solid rectangle of area K×min(hi,hi+1,…,hi+k−1)K×min(hi,hi+1,…,hi+k−1).

Given NN buildings, find the greatest such solid area formed by consecutive buildings.

Link

Largest Rectangle

Complexity:

time complexity is O(N)

space complexity is O(N)

Execution:

Best explained on Geeks for Geeks.

Solution:
def computeLargestArea(hist, N):
    stack = []
    
    max_area = 0
    
    idx = 0
    while (idx < N):
        if not stack or hist[stack[-1]] <= hist[idx]:
            stack.append(idx)
            idx += 1
        else:
            
            height_idx = stack.pop()
            
            depth = idx
            if stack:
                depth = idx - stack[-1] - 1
            
            area = hist[height_idx] * depth
            max_area = max(area, max_area)
     
    while stack:
        height_idx = stack.pop()
            
        depth = idx
        if stack:
            depth = idx - stack[-1] - 1
            
        area = hist[height_idx] * depth
        max_area = max(area, max_area)
            
    return max_area

def main():
    N = int(raw_input())
    
    hist = map(int, raw_input().split())
    
    print computeLargestArea(hist, N)
    


if __name__ == '__main__':
    main()

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin