Largest Rectangular Area In Histogram Using Segment Tree In C++

Histograms serve as a fundamental data structure in the realm of computer science, finding applications in tasks such as data examination and image manipulation. A common problem often faced is identifying the largest rectangular area enclosed within a histogram. This article will explore a swift and efficient approach to tackling this problem by utilizing a Segment Tree data structure in C++.

Understanding the Problem:

Consider a bar graph illustrating the occurrence or spread of data, known as a histogram. The objective is to identify the largest rectangular area that can be enclosed within it. Each bar in the histogram represents a distinct height, and the neighboring bars with heights equal to or higher than the current bar's height establish the breadth of the rectangular region.

1. Naive Approach:

Viewing each column in the histogram as a potential starting point for a rectangle is a straightforward approach to solving this problem. By expanding horizontally from each column until reaching a shorter column, we can calculate the area and keep track of the largest area found.

• ✅ This technique becomes inefficient for large histograms because of its time complexity of O(n^2), where 'n' represents the histogram's number of columns.
• ✅ A more efficient approach involves leveraging a Segment Tree, a versatile data structure commonly applied in problems requiring range queries, to efficiently determine the maximum rectangular area within a histogram. Here is how this efficient technique functions:

Efficient Approach Using Segment Tree:

• ✅ First, create a segmentation tree based on the heights of the histogram.
• ✅ Next, go from left to right throughout the histogram, and find the first bar on the left and right with a lower height for each bar.
• ✅ After that, determine the minimal height and breadth of the rectangular area that can be constructed with the current bar based on the places identified in Step 2.
• ✅ Record the largest area discovered throughout the traversal.

Program:

Let's consider an illustration to find the maximum rectangular area in a histogram by employing a segment tree in C++.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// Function to find the largest rectangular area in the histogram
int largestRectangleArea(vector<int>& histogram) {
 stack<int> s;
 int maxArea = 0;
 int i = 0;
 while (i < histogram.size()) {
 if (s.empty() || histogram[i] >= histogram[s.top()]) {
 s.push(i);
 i++;
 } else {
 int tp = s.top();
 s.pop();
 int width = s.empty() ? i : i - s.top() - 1;
 maxArea = max(maxArea, histogram[tp] * width);
 }
 }
 while (!s.empty()) {
 int tp = s.top();
 s.pop();
 int width = s.empty() ? i : i - s.top() - 1;
 maxArea = max(maxArea, histogram[tp] * width);
 }
 return maxArea;
}
int main() {
 vector<int> histogram = {2, 1, 5, 6, 2, 3};
 int maxArea = largestRectangleArea(histogram);
 cout << "Largest Rectangular Area in the Histogram: " << maxArea << endl;
 return 0;
}

Output:

Code Explanation:

• ✅ Iteration over Histogram: In this example, we cycle through each bar in the histogram from left to right.
• ✅ Bar Indices Stack: We keep the bar indices in ascending order of height in a stack, which can be accomplished with a vector or other comparable data structure.
• ✅ Keeping the Stack Together: We decide when to pop bar indices off the stack and when to push them on when iterating across the histogram.
• ✅ Stack Bar Index onto Stack: We put the current bar's index onto the stack when we come across a bar whose height is greater than or equal to the bar at the top of the stack?or if the stack is empty. By doing this, the stack is guaranteed to retain the indices of bars that could help create larger rectangles.
• ✅ Bars of Pop From Stack: We begin popping bars from the stack whenever we come across a bar whose height is less than the bar at the top of the stack. We determine the area that can be formed by each popped bar by measuring its height and width (the difference between the present position and the top of the stack).
• ✅ Max Area Updating: If the calculated area is more than the current maximum, we update the maximum area as we calculate the area for each popping bar.
• ✅ Iterate the Procedure: Until we either reach the end of the histogram or come across a bar that is lower in height than the bar at the top of the stack, we keep pushing and popping bars.
• ✅ Bars Still in the Stack: There might be some bars in the stack left behind after processing every bar in the histogram. We keep popping bars and figuring out areas until the stack is empty.
• ✅ Maximum Area: The largest rectangular area that can be formed in the histogram is the maximum area that is encountered during this operation.