Given the heights of histogram using an array, you need to find the largest area rectangle in that histogram. Solution in C++

Question explanation:
A histogram is a bar graph, where each unit is 1. You are given an array representing the height of the histogram. You need to find the maximum area of the histogram.

Suppose given array is as below:
{ 4, 2, 5, 4, 5, 1}

The histogram can be shown as below:

So from the above histogram we need to find the largest area.

If we can glance the above image, we can see that the first 5 columns with height 2. As shown in the image below (in blue color):

The area here is 5[column] * 2 [height]= 10 units.

But on further analysis we can find another area that is greater than the present area. It is shown in pic below:

Here the area is 3[column] * 4[height] = 12 units. Clearly this area is greater than the current area.

So we understood that, we need to find all the area and in those areas we need to find the area with largest units.

We can solve this problem by below methods.
1. Brute force with time complexity O(n^2)
2. Divide and Conquer with time complexity of O(nlog n)
3. Stack based with time complexity of O(n)

In this tutorial we shall look at the stack based solution.

Below are the steps to be performed for stack based solution:

1. Add the element to the stack if the current element value is greater than or equal to the top of the stack.
2. If the current element is lesser than the stack, remove the elements from the stack, till we find an element value, that is lesser than or equal to the current element.
3. While removing, calculate the area by using below formula:
a. If the stack is empty
area = array[top] * i
else
area = array[top] * [i – stack_top – 1]

Solution in C++

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int get_max_area_using_stack(vector<int>& array) 
{
    array.push_back(0);
    int size = array.size();
    stack<int> Stack;
    int i = 0, max_a = 0;
    while (i < size) 
    {
        if (Stack.empty() || array[i] >= array[Stack.top()]) 
            Stack.push(i++);
        else 
        {
            int h = Stack.top();
            Stack.pop();
            max_a = max(max_a, array[h] * (Stack.empty() ? i : i - Stack.top() - 1));
        }
    }
    return max_a;
}

int main()
{
    vector<int> array;
    array.push_back(2);
    array.push_back(1);
    array.push_back(5);
    array.push_back(6);
    array.push_back(2);
    array.push_back(3);

    int max_area = get_max_area_using_stack(array);
    cout<<"The max area is = "<< max_area<<endl;

    return 0;
}

Output:
The max area is = 10