The largest rectangular problem
Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.
This is one particular manifestation of the all nearest smaller values (ANSV) (
AllNearestSmallerValue) problem. For each bar in the histogram, we want to find the nearest bar on the left which is shorter, and the nearest bar on the right which is shorter—because they determine how far left and how far right we can extend a rectangle with the current bar’s full height. Use the O(n) stack-based algorithm for ANSV, and the problem becomes trivial.
- Take 2 arrays (one-one for left and right width of a bar ) and one stack to hold index to calculate ANSV.
- Now calculate left width
- Push 0 in add stack
left = 0
- Iterate given histogram array from index 1 to n
histogram[stack.top] >= histogram[i] && stack is not emptythen
- If stack is empty then,
left[i] = i + 1
left[i] = i - stack.top()
- Populate right[i] same way as we did for left area but from nth to 0th index of histogram
- Now calculate Area
MaxArea = 0
- Iterate given histogram array from index 0 to n
width = left[i] + right[i] - 1
Set area = width * histogram[i]
MaxArea < areathen
Set MaxArea = area
Latest Source Code:
Largest Rectangle Area: 12 Largest Rectangle Area: 8