Largest rectangle in a histogram is an interesting puzzle and can be solved in several different ways. One of the most popular O(n) method involves usage of stack, another one employs memoization to improve on the brute force approach, and then there is also a slightly slower O(nLog(n)) method employing segment tree. Evidently this problem seems quite useful for illustrating some of the data structure and programming concepts.
Below diagram is an illustration of such a histogram represented by an array with heights { 2, 1 ,5, 6, 2, 3}.
The Problem
We are essentially seeking the largest rectangle within a histogram. And the two variables determining the area of such a rectangle would be the minimum height among the included bars and the total number of bars. For example, in the above histogram the maximum area would be formed by two bars at the offset 2 and 3 with a minimum height equal to 5, so 5 x 2 = 10 .
Area = Minimum_Height x Number of bars
The search for that elusive maximum area requires us to scan all the possible rectangles in the histogram. This can either happen by picking a bar and then seeking the maximum range where its own height is the minimum. Or by picking a range and then finding the minimum height. In other words, we pick a value for one variable in the above equation and then proceed to find a valid measurement for the other one.
O(n) Approach
If we sequentially pick each element and then locate the smaller bar to the left and right, then we would have the width of the rectangle corresponding to each height/bar. In this manner we can eventually figure out the largest rectangle. A brute force O(n^2) approach would simply involve two nested loops, outer loop to sequentially pick the element and the inner loop to scan the values to the left and right of that selected bar.
The above diagram illustrates the basic idea behind this algorithm. Performance would eventually depend on how quickly we can identify this width corresponding to each rectangle. We can explore how the usage of stack and memoization can essentially improve the time taken for this scan.
Stack: The idea is to push array elements into a stack as long as the present top of the stack is shorter than the element being pushed. If the stack top is larger than the element, then the present element provides the right hand side offset for the width, so now we can calculate the area of the rectangle with top element as the height. Note that the left offset can be identified by checking the stack element right below the top. After calculating the area, pop the stack. Repeat this operation as long as the top of the stack is larger than the present element. So at any instant the stack would only contain those elements whose left offset is identified but not the right.
The above diagrams illustrate how the stack operations would scan the array { 2, 1, 5, 6, 2, 3}. As you can see, space complexity would also be O(n).
/* Push the first element into the stack */
spush(&s, &a[0]);
b = a[0];
/* Scan all the elements */
while (i < n)
{
/* The bar is higher than stack top, push
into the stack */
if (a[i] >= b)
{
spush(&s, &a[i]);
b = a[i];
}
/* Else we need to calculate the area spanned by the
bar on the top of the stack. */
else
{
/* Peek while the stack top is less than the present
bar */
while ((speek(&s, &offst, &b) == 0) && (b > a[i]))
{
int loffst, ht;
/* Pop and then peek into the stack to get the
left offset */
spop (&s, &offst, &b);
speek(&s, &loffst, &ht);
/* Update the max rectangle */
if (max_rectangle < (b * ((i - loffst - 1))))
max_rectangle = b * (i - loffst - 1);
}
/* Push the bar into the stack */
spush(&s, &a[i]);
b = a[i];
}
/* Move to the next bar */
++i;
}
/* Pop the remaining bars */
while (spop(&s, &offst, &b) == 0)
{
int loffst, ht;
/* Update the area */
speek(&s, &loffst, &ht);
if (max_rectangle < (b * (i - loffst - 1)))
max_rectangle = b * (i - loffst - 1);
}
/* Return maximum area */
free(s.s);
return max_rectangle;
Relevant piece of code is provided above, for more details please refer to the source code repository link.
Memoization: A brute force approach to this problem would require us to scan the left and right sub-arrays for each element looking for the relevant shorter height. For example, the bar with height 1 in the above example would force scanning of the whole array. In that sense if all the bars were of equal height, then the brute force algorithm would always force n^2 comparisons. Memoization involves caching and utilizing the already scanned information for subsequent use. Seems like that approach is an ideal candidate here.
The above diagram illustrates how the relevant smaller right offset for each element can be recorded by scanning the array in the reverse order. Please note that the curved arrow pointers signify comparisons within the inner loop. The crucial aspect is that by using the already recorded offsets we can leapfrog certain locations which are not relevant for that element.
For example, with this new method, generation of offset values until the location 2 (having value 5) does not see any reduction in number of comparisons. But the calculation of right offset for value 1 at the array location 1 was reduced by less than half because of the already cached offset value. How? We know that the value 5 is greater than 1, and we also know the offset of the value which is smaller than 5 (ie: 2 at location 4). So, we can conveniently jump to location 4 and check whether the value at that offset (ie:2) is less than 1, the search ends if it is smaller, else we merely jump to the next recorded offset (ie:6, end of list).
Similarly the smaller left offset values can also be generated by scanning the array, but this time in the order from the start. With the allocated additional space for memoization, we manage to short-circuit the comparison sequence. Once we have the left and right offsets for all the elements, we can simply run through the array and calculate the maximum area.
/* First element has no left smaller element, last element has no
right smaller */
smaller_left[0] = -1;
smaller_right[n - 1] = n;
for (i = 1; i < n; ++i)
{
/* Best case */
if (a[i] > a[i - 1])
smaller_left[i] = i - 1;
/* Else scan the array */
else
{
int x = i - 1;
/* Look for the next smaller element towards the left */
while ((x >= 0) && (a[x] >= a[i]))
x = smaller_left[x];
/* Found the offset for the next smaller element */
smaller_left[i] = x;
}
}
/* Generate the offsets for smaller elements to the right */
for (i = n - 2; i >= 0; --i)
{
/* Best case */
if (a[i + 1] < a[i])
smaller_right[i] = i + 1;
/* Else scan the array */
else
{
int x = i + 1;
/* Loop as long as the values at the offsets are greater
than a[i] */
while ((x < n) && (a[x] >= a[i]))
x = smaller_right[x];
/* Smaller to the right */
smaller_right[i] = x;
}
}
/* O(n) scan to get the maximum area */
for (i = 0; i < n; i++)
{
int mi = a[i] * (smaller_right[i] - smaller_left[i] - 1);
if (max_rectangle < mi)
max_rectangle = mi;
}
/* Return maximum area */
return max_rectangle;
Essential piece of code is given above, for more details please refer to the source code repository link.
O(nLog(n)
The third method is slightly more elaborate, it involves a segment tree. Since this data structure can be used for quickly finding the minimum value within a sub-array, we can use that property to implement a divide and conquer algorithm. In other words, armed with a segment tree hammer, this problem starts to look like a nail. The point is by using a segment tree the minimum height within any range can be found in logarithmic time . So here our approach would involve dividing the histogram while calculating the minimum height within each such divisions.
So first we start with the whole histogram, basically we pick the maximum width and then find the corresponding height. Then we divide the histogram based on the offset of the bar with this minimum height and recursively repeat the same operation on each sub-division. The idea is illustrated in the below diagram.
int seg_tree(int *a, int *arr, int s, int e, int len)
{
int min, lmax, rmax, mmax;
/* Recursion termination */
if (s > e)
return 0;
/* Get the minimum value offset */
min = search_sg_tree(arr, a, 0, s, e, 0, len - 1);
/* Calculate the area with the minimum value within this offset */
mmax = a[min] * (e - s + 1);
/* Go to the left subtree */
lmax = seg_tree(a, arr, s, min - 1, len);
/* Go to the right subtree */
rmax = seg_tree(a, arr, min + 1, e, len);
/* Return the max */
return (((mmax > lmax) ? mmax : lmax) > rmax) ?
((mmax > lmax) ? mmax : lmax) : rmax;
}
As you can see, depth of the recursive calls in the above divide and conquer method eventually depends on how the array actually gets divided during each call. If all the values are equal, then it will lead to the worst case scenario where the call stack depth is equivalent to n. In other words, the call stack memory usage complexity is O(n).
Segment Tree used for the above algorithm is given below:
We can implement such a segment tree using an array data structure, address of the left and right children can be easily generated using the formula (Parent_Offset * 2 + 1) & (Parent_Offset * 2 + 2), quite like a heap. Below figure illustrates the above segment tree when it’s structured like an array.
As you can see, some of the locations remain unused. A tree of depth 4 can hold upto 16 elements, but this array requires only 11 locations. Generation of a segment tree is also quite similar to how an array would be converted to binary tree. Basically, we recursively generate the sub-trees while allowing the smaller child to rise to the top. Within such a tree, the smallest sub-tree would be the leaf nodes which would hold the array values and that also determines the terminating condition for recursion.
/***********************************************************************/
/* create_sg_tree: Create a segment tree from an array */
/* */
/***********************************************************************/
int create_sg_tree(int *arr, int soff, int s, int e, int *a, int len)
{
int mid;
/* We are at the leaf node */
if (s == e)
return s;
/* Calculate the middle of the array */
mid = s + ((e - s + 1) / 2) - 1;
/* Set the left subtree root node */
arr[(soff * 2) + 1] = create_sg_tree(arr, (soff * 2) + 1, s,
mid, a, len);
/* Set the right subtree root node */
arr[(soff * 2) + 2] = create_sg_tree(arr, (soff * 2) + 2,
mid + 1, e, a, len);
/* Allow the smaller value to rise to the top */
return a[arr[(soff * 2) + 1]] > a[arr[(soff * 2) + 2]] ?
arr[(soff * 2) + 2] : arr[(soff * 2) + 1];
}
For more details please refer to the source code repository.
Generation of the segment tree is O(Log(n)), and we sequentially pick n elements and find the smallest within the relevant range with Log(n) complexity. Overall O(nLog(n)).
Embedded Sense 