Problem: Largest Rectangle
Solution 1: Using for loop and if-else statement
Time Complexity: O(n^2) - (TLE)
1
2
3
4
5
6
7
8
def largestRectangle(h):
max_area = 0
for i in range(len(h)):
min_height = h[i]
for j in range(i, len(h)):
min_height = min(min_height, h[j])
max_area = max(max_area, min_height * (j - i + 1))
return max_area
Solution 2: Using loops
Time Complexity: O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def largestRectangle(h):
# Write your code here
n = len(h)
m = 0
for i in range(n):
j = i
ans = 0
while 0 <= j :
if h[j] >= h[i]:
ans += h[i]
else:
break
j -= 1
j = i + 1
while j < n:
if h[j] >= h[i]:
ans += h[i]
else:
break
j += 1
m = max(m, ans)
return m