HackerRank ‘Largest Rectangle’ Solution

H
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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()

About the author

Add comment

Archives

Categories