Here is the interview question prompt, presented for reference.
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:
const 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?
You can see the full challenge with visuals at this link.
Challenges • Asked 10 months ago by Will Bowers
This is the main discussion thread generated for Max Rectangle In A Histogram.
The third test case is wrong. The hist [1, 2, 3, 4] has a rect of size 6. 4 is not the max.
+1 to Will's comment - maxRectArea is 6 for [1, 2, 3, 4] either horizontally using indices (1, 2, 3) or vertically using indices (2, 3)
Final solution is wrong.
In line 7, code should be
while index < len(histArr):
@Will, @Stu, @louis19930910,
Thank you for your support. Now the code along with the test cases are fixed for all languages. Happy Coding!