Histogram Area Problem Using C++

Filed Under: C++
Histogram Area Problem Using C

In today’s article, we’ll learn to solve the histogram area problem using C++. This is very popular related to technical interviews. There are high chances for your recruiter to ask about this problem during a technical coding interview.

Today we’ll find the solution to this problem using the stack-based approach. It’s going to be interesting, so without wasting any time, let’s get started.

What Is A Histogram?

Before we move to the problem statement, let’s quickly go through a histogram. Let’s see how does it look like and what it means.

Histogram
Histogram

Using a histogram, we represent the frequency of a variable and observe how frequently this variable falls into a particular bin.

Problem Statement for Histogram Area Problem in C++

Given a histogram, find the maximum area that you can get by making a rectangle in this histogram. Take the width of each bar as 1 unit.

Concept for Histogram Area Problem

There are many rectangles possible. Out of all these rectangles, our task is to find the one with the maximum area. It is a classical data structure and algorithm problem, so there are multiple ways to solve this problem. In this article, we’ll go with the stack-based approach. Let’s go through the pseudocode and get the intuition behind the algorithm.

Example
Example
  • Create a stack of integers. This stack will contain the indices of the elements of the array
  • Now for each bar of the histogram, we will do the following
    • Push the bar into the stack if it’s of higher value than the stack top.
    • Otherwise, pop all the bars of greater height than the current bar.
  • Based on the above two operations, governing formulas for the area will be:
    • if(stack.empty())
      • area = arr[top] * i
    • else
      • area = arr[top] * (i – s.top() – 1)
      • Here, i represent the rightmost lower element
      • And s.top() represent the previous top element(left)

Algorithm for Histogram Area Problem in C++

// function to calculate the maximum area
int maximum_area(vector <int> arr)
{
	int n = arr.size();
	int max_area = 0;
	stack <int> s;

    // start iterating over the elements
	for(int i = 0; i < n; i++)
	{
        // check if the stack is empty or not
		while(!s.empty())
		{
            // Case: Current bar is greater than or
            // equal to the previous bar(push)
			if(arr[s.top()] <= arr[i])
				break;

            // Case: Current bar is smaller than the
            // previous bar(pop)
			int j = s.top();
			s.pop();

            //  Area calculation formulas
			if(!s.empty())
				max_area = max(max_area, arr[j] * (i - s.top() - 1));
			else
				max_area = max(max_area, arr[j] * i);
		}

		s.push(i);
	}

    // if the stack is still not empty,
    // calculate the area again
	while(!s.empty())
	{
		int j = s.top();
		s.pop();
		
		if(!s.empty())
			max_area = max(max_area, arr[j] * (n - s.top() - 1));
		else
			max_area = max(max_area, arr[j] * n);
	}

	return max_area;
}

Histogram Area Problem in C++

Histogram Area Code
Histogram Area Code
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int maximum_area(vector <int> arr)
{
	int n = arr.size();
	int max_area = 0;
	stack <int> s;

	for(int i = 0; i < n; i++)
	{
		while(!s.empty())
		{
			if(arr[s.top()] <= arr[i])
				break;

			int j = s.top();
			s.pop();

			if(!s.empty())
				max_area = max(max_area, arr[j] * (i - s.top() - 1));
			else
				max_area = max(max_area, arr[j] * i);
		}

		s.push(i);
	}

	while(!s.empty())
	{
		int j = s.top();
		s.pop();
		
		if(!s.empty())
			max_area = max(max_area, arr[j] * (n - s.top() - 1));
		else
			max_area = max(max_area, arr[j] * n);
	}

	return max_area;
}

int main()
{
	vector <int> histogram;
	cout << "Enter the height of each bar of the histogram, press -1 to stop" << endl;

	while(true)
	{
		int ele;
		cin >> ele;

		if(ele == -1)
			break;

		histogram.push_back(ele);
	}

	cout << "The maximum area under the current histogram is: " << maximum_area(histogram) << endl;

	return 0;
}

Output

Histogram Area Output
Histogram Area Output

Conclusion

In this article, we learned to solve the maximum histogram area problem. Being a classical problem, it is very important for interview preparation and conceptual understanding of the subject. We used the stack-based approach to find the solution to this problem. If you notice the time complexity of the algorithm, you’ll find it to be linearly proportional to the size of the vector, i.e. O(N). This is one of the most efficient approaches to solving this problem. That’s all for today, thanks for reading.

Further Readings

To learn more about data structures and algorithms, you can refer to the following articles.

https://www.journaldev.com/60947/rotate-images-using-cpp

https://www.journaldev.com/60975/sum-subarray-in-a-sorted-2d-matrix-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors