Good morning! Here's our prompt for today.
We're given a histogram like the following, where contiguous (sharing a common border or touching) bars are made up of different heights. Let's assume all bars have the same width.

The histogram is converted to an array of the heights of the bars:
JAVASCRIPT
1const histArr = [3, 1, 4, 2, 2, 1]
With this knowledge, can we find the largest rectangular area within the histogram? For the above, it would be the area outlined below:

With the above histogram, calling maxRectInHist(histArr)
would get us 6
. Can you fill in the method?
Constraints
- Length of the array <=
100000
- The array can be empty
- The array will contain values between
1
and10000
- The final answer will always fit in the integer range
- Expected time complexity :
O(n)
- Expected space complexity :
O(n)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
26
def maxRectInHist(histArr):
# fill in
return histArr
​
​
import unittest
​
​
class Test(unittest.TestCase):
def test_1(self):
assert maxRectInHist([3, 1, 4, 2, 2, 1]) == 6
print("PASSED: assert maxRectInHist([3, 1, 4, 2, 2, 1]) == 6")
​
def test_2(self):
assert maxRectInHist([]) == 0
print("PASSED: assert maxRectInHist([]) == 0")
​
def test_3(self):
assert maxRectInHist([1, 2, 3, 4]) == 6
print("PASSED: assert maxRectInHist([1, 2, 3, 4]) == 6")
​
​
if __name__ == "__main__":
unittest.main(verbosity=2)
print("Nice job, 3/3 tests passed!")
​
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.