Community

Ask A Question


Notifications
Subscribe You’re not receiving notifications from this thread.

Max Rectangle In A Histogram (Main Thread)

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:

js 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?

Constraints

  • Length of the array <= 100000
  • The array can be empty
  • The array will contain values between 1 and 10000
  • The final answer will always fit in the integer range
  • Expected time complexity : O(n)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked 5 months ago by Will Bowers

Jake from AlgoDaily Commented on Aug 30, 2020:

This is the main discussion thread generated for Max Rectangle In A Histogram.

Will Bowers Commented on Aug 30, 2020:

The third test case is wrong. The hist [1, 2, 3, 4] has a rect of size 6. 4 is not the max.