Skip to content

Instantly share code, notes, and snippets.

@uztbt
Created January 23, 2021 12:39
Show Gist options
  • Save uztbt/67c98ea5e8d5b8047fc92097fdaa026d to your computer and use it in GitHub Desktop.
Save uztbt/67c98ea5e8d5b8047fc92097fdaa026d to your computer and use it in GitHub Desktop.
My solution to a Hacker Rank problem "Largest Rectangle"
# My solution to https://www.hackerrank.com/challenges/largest-rectangle/problem?h_r=internal-search
def largestRectangle(h: list):
stack = [(0, 0)]
h.append(0)
largest = 0
for i, height in enumerate(h, 1):
tallest = stack[-1]
leftWall = i
while tallest[0] > height:
largest = max(
largest,
tallest[0] * (i - tallest[1])
)
stack.pop()
leftWall = tallest[1]
tallest = stack[-1]
if tallest[0] == height:
pass
else:
# tallest[0] < height
stack.append((height, leftWall))
return largest
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment