# 91 ms python solution with constant space

• def largest_rectangle(height):
n = len(height)
if n < 2:
return height[0] if n else 0

height.append(0)
max_area = 0
for i in range(0, n + 1):
j = i - 1
while j >= 0 and height[j] > height[i]:
max_area = max(max_area, height[j] * (i - j))
height[j] = height[i]
j -= 1
return max_area

• It's concise and like a magic, but I cannot understand the algorithm in your code.
Why you use 'height[j] = height[i]'
I would appreciate if you can explain all.

• In i th iteration, height[j] = height[i] for all j >= 0 and height[j] > height[i] effectively makes height[:i] non decreasing, which is equivalent to using a stack that stores the indices of elements that are in non decreasing order.

• In my opinion, this can't be considered as constant space because you reused the input space.

• As "commented" said it is not true constant space

I modified code a bit to make it really constant space.. And I think it will be easier to read and understand.

Basically when a height drop detected, the code searches potential largest area that will not be seen as the algorithm goes on running.

BTW I think this is a greedy algorithm

def largestRectangleArea(self, height):
if not height: return 0

lens = len(height)
maxArea = 0
for r in range(0,lens):
if height[r] > height[r+1]:
l = r
minInrange = height[r]
while height[l] > height[r+1] and l >= 0:
minInrange = min(minInrange, height[l])
maxArea = max(maxArea, minInrange*(r-l+1))
l -= 1
return maxArea

• what's the complexity? Seems to be O(n^2)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.