How Do You Find The Maximum Rectangular Area In A Histogram Using A Stack In C++

Introduction:

To determine the largest possible rectangular Area within a histogram by employing a stack in C++, we can utilize a technique that exploits the characteristics of stacks to monitor the indexes of histogram bars effectively. By adopting this method, we can minimize the number of iterations required to traverse the histogram bars, thereby enhancing the efficiency of the computation.

The fundamental concept involves utilizing a stack to keep track of the positions of the bars in the histogram while ensuring they are in ascending order based on height. As we go through the histogram, we execute the following actions as outlined below:

• ✅ Add to Stack: If the current bar's height is equal to or greater than the height of the bar at the index stored at the top of the stack, we add the current index to the stack.
• ✅ Remove from Stack and Compute Area: Upon encountering a bar shorter than the one at the top of the stack, it signifies the end of the width of a rectangle. Subsequently, we remove an element from the stack, treating the removed index as the rectangle's height, and determine the Area using the width calculated by the disparity between the current index and the index of the new top of the stack.

Approach 1: Simple Approach

Implementation:

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int getMaxArea(vector<int>& hist) {
    stack<int> s;
    int max_area = 0;
    int tp;
    int area_with_top;
    int i = 0;
    while (i < hist.size()) {
        if (s.empty() || hist[s.top()] <= hist[i]) {
            s.push(i++);
        } else {
            tp = s.top();
            s.pop();
            area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
            max_area = max(max_area, area_with_top);
        }
    }
    while (!s.empty()) {
        tp = s.top();
        s.pop();
        area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
        max_area = max(max_area, area_with_top);
    }
    return max_area;
}
int main() {
    vector<int> hist = {6, 2, 5, 4, 5, 1, 6};
    cout << "Maximum rectangular area is " << getMaxArea(hist) << endl;
    return 0;
}

Output:

Maximum rectangular Area is 12

Explanation:

Initialize Data Structures:

• ✅ Begin by establishing an empty stack designed to store the indices of the histogram bars.
• ✅ Set up a variable to monitor the maximum Area discovered, starting with a value of zero.

Traverse the Histogram:

Initiate the process of moving through the histogram starting from the initial bar and progressing towards the final bar.

Handle Rising Elevations:

When examining each column in the histogram, if the stack is vacant or the present column is as tall as or taller than the column at the top index of the stack, the current index is added to the stack. This process involves constructing a series of ascending column heights.

Calculate Area on Decreasing Height:

• ✅ If the current bar is shorter than the bar at the index on top of the stack, it indicates the end of a sequence of increasing heights.
• ✅ Pop the top index from the stack, considering it as the height of a rectangle.
• ✅ Calculate the width of this rectangle:
• ✅ If the stack is now empty, the width spans from the start to the current index.
• ✅ If the stack is not empty, the width is the difference between the current index and the new top index of the stack minus one (since the new top index indicates the start of the next rectangle).
• ✅ Calculate the Area of the rectangle using the popped height and the computed width.
• ✅ Update the maximum Area if this newly calculated Area is larger.

Continue Navigating:

• ✅ Proceed with this procedure of updating indexes and computing areas each time a smaller bar is found until reaching the conclusion of the histogram.

Process Outstanding Index Values:

Once the iteration is finished, there may still be indices left within the stack. These particular indices signify bars that formed a rising sequence until the conclusion.

Remove each remaining index from the stack and compute the Area following the same method outlined previously. This guarantees that all probable rectangles are taken into account.

Output the Maximum Area:

• ✅ Ultimately, the variable for maximum area will store the largest rectangular area discovered throughout the procedure.

Let us see the Example for a Better understanding:

Consider the histogram [6, 2, 5, 4, 5, 1, 6]:

Start with an empty stack and max area 0.

Traverse each bar:

• ✅ For 6: Stack is empty, push index 0.
• ✅ For 2: 2 is less than 6, pop 0, calculate Area 6x1=6, update max Area to 6, push index 1.
• ✅ For 5: Push index 2.
• ✅ For 4: 4 is less than 5, pop 2, calculate Area 5x1=5, max Area remains 6, push index 3.
• ✅ For 5: Push index 4.
• ✅ For 1: 1 is less than 5, pop 4, calculate Area 5x1=5, max Area remains 6. Then pop 3, calculate Area 4x3=12, update max Area to 12. Push index 5.
• ✅ For 6: Push index 6.

Process the remaining indexes:

• ✅ Remove 6, compute the area 6x1=6, the maximum area still stands at 12.
• ✅ Remove 5, determine the area 1x7=7, the maximum area remains at 12.

Thus, the maximum rectangular Area is 12.

Complexity Analysis:

Time Complexity:

The algorithm's time complexity is O(n), with n representing the quantity of bars in the histogram.

Single Pass: The algorithm iterates through the histogram bars in a single sweep from left to right.

Insert and Remove Operations: Every index is inserted into the stack once and removed from the stack once. As each insertion and removal operation has a constant time complexity, the overall number of operations is directly proportional to the total number of bars.

Thus, the overall time complexity is O(n).

Space Complexity:

The algorithm's space complexity is O(n). Below is the detailed analysis:

Stack Implementation: In the most unfavorable scenario where all bars are arranged in ascending order, each bar's index will be added to the stack, resulting in the stack holding n indices.

The storage allocated for extra variables (such as maxarea, i, tp, areawith_top) remains consistent and is not influenced by the input size.

Thus, the overall space complexity is O(n).

Approach 2: using Divide and Conquer Approach:

This method is influenced by the algorithm employed to determine the highest subarray total, and it includes segmenting the histogram into smaller subtasks and addressing each one through recursion.

Implementation:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int getMinIndex(const vector<int>& hist, int start, int end) {
    int minIndex = start;
    for (int i = start + 1; i <= end; ++i) {
        if (hist[i] < hist[minIndex]) {
            minIndex = i;
        }
    }
    return minIndex;
}
int getMaxAreaHelper(const vector<int>& hist, int start, int end) {
    if (start > end) {
        return 0;
    }
    int minIndex = getMinIndex(hist, start, end);
    int leftArea = getMaxAreaHelper(hist, start, minIndex - 1);
    int rightArea = getMaxAreaHelper(hist, minIndex + 1, end);
    int minArea = hist[minIndex] * (end - start + 1);
    return max(minArea, max(leftArea, rightArea));
}
int getMaxArea(const vector<int>& hist) {
    return getMaxAreaHelper(hist, 0, hist.size() - 1);
}
int main() {
    vector<int> hist = {6, 2, 5, 4, 5, 1, 6};
    cout << "Maximum rectangular area is " << getMaxArea(hist) << endl;
    return 0;
}

Output:

Maximum rectangular Area is 12

Explanation:

Step 1: Problem Definition

Imagine you are given a histogram depicted as an array of bar heights. The objective is to calculate the maximum area of a rectangle that can be created within these bars.

Step 2: Base Case

The most basic situation occurs when the histogram is devoid of any data or when analyzing a range that does not contain any bars. In these instances, the maximum area of a rectangle is zero.

Step 3: Finding the Minimum Bar

For each specific range of bars in the histogram, pinpoint the bar with the lowest height. This particular bar plays a vital role because:

• ✅ It serves as a constraint on the height of any rectangle that covers the full span within the range.
• ✅ It organically partitions the histogram into two distinct sub-histograms: one on the left side of this bar and one on the right side.

Step 4: Recursively Solving Subproblems

Once you identify the smallest threshold that separates the histogram:

Left Sub-histogram: Analyze the columns located to the left of the smallest column. Calculate iteratively the largest possible area that can be enclosed within this section on the left.

Right Sub-histogram: In the same manner, analyze the bars located to the right of the smallest bar. Continuously search for the largest rectangular area within this right section.

Step 5: Combining Results

To find the overall maximum rectangular Area for the current range:

• ✅ Area Spanning the Minimum Bar: Calculate the Area of the rectangle that includes the minimum bar and spans the entire width of the current range. This Area is simply the height of the minimum bar multiplied by the number of bars in the current range.
• ✅ Maximum of All Areas: Compare the three areas obtained:
• ✅ Maximum Area from the left sub-histogram.
• ✅ Maximum Area from the right sub-histogram.
• ✅ The Area that spans the minimum bar.

The most significant among these three regions corresponds to the solution for the present set of bars.

Step 6: Recursive Approach

Repeat the aforementioned steps for each sub-histogram generated by identifying the smallest bar until all potential sub-histograms have been handled.

Example:

Let's implement this technique on a sample histogram [6, 2, 5, 4, 5, 1, 6].

Begin with the complete set of bars in the initial histogram.

Locate Lowest Bar: The smallest bar within the range is 1, positioned at index 5.

Divide and Conquer:

• ✅ Left Sub-histogram: Bars [6, 2, 5, 4, 5]
• ✅ The minimum bar is 2 at index 1.
• ✅ Further divide into [6] and [5, 4, 5].
• ✅ Right Sub-histogram: Bars [6]

Calculate Areas:

Left side: The largest possible area is 6 when considering a single element [6], and it increases to 9 when looking at the subset [5, 4, 5].

Right Part: Maximum Area is 6 from [6].

Span Smallest Bar: The area covered by the smallest bar, bar 1, is 7 units (height 1 * width 7).

The greatest among these regions is 12 units away from the beginning of the left sub-histogram [5, 4, 5].

Complexity analysis:

Time Complexity:

The time complexity of employing the Divide and Conquer strategy to determine the maximum rectangular area within a histogram may differ depending on the histogram's configuration.

Finding the Smallest Bar: Whenever we identify the smallest bar within a sub-histogram, it requires O(n) time for the complete histogram, O(n−1) for one side post division, and so forth.

Recursive Divisions: Every partition generates two fresh subtasks. If the histogram is pre-sorted in ascending or descending order, the scenario may require n recursive invocations, each with a time complexity of O(n).

In the most unfavorable situation, the time complexity reaches its peak.

O(n)+O(n-1)+O(n-2)+…+O(1)=O(n2)

Consequently, the maximum time complexity in the worst-case scenario is O(n2).

Space complexity:

The space efficiency is predominantly influenced by the stack of recursive calls utilized in the Divide and Conquer strategy.

In the most unfavorable scenario, when the histogram is segmented in a manner where each subtask diminishes by just one element, the recursion stack's depth may reach up to n.

Other variables employed within the function (such as those for retaining the smallest index and the calculated areas) consume fixed space that remains unaffected by the input size.

Approach 3: using Dynamic Programming Approach:

This technique requires calculating in advance the width of the biggest rectangle that can be created up to each bar, and subsequently leveraging these widths to determine the maximum area.

Implementation:

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int getMaxArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n);
    stack<int> s;
    // Fill left limits
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            s.pop();
        }
        left[i] = s.empty() ? -1 : s.top();
        s.push(i);
    } 
    // Clear the stack to reuse it for the right limits
    while (!s.empty()) {
        s.pop();
    }
    // Fill right limits
    for (int i = n - 1; i >= 0; --i) {
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            s.pop();
        }
        right[i] = s.empty() ? n : s.top();
        s.push(i);
    }
    // Calculate maximum Area
    int maxArea = 0;
    for (int i = 0; i < n; ++i) {
        int width = right[i] - left[i] - 1;
        int area = heights[i] * width;
        maxArea = max(maxArea, area);
    }
    return maxArea;
}
int main() {
    vector<int> hist = {6, 2, 5, 4, 5, 1, 6};
    cout << "Maximum rectangular area is " << getMaxArea(hist) << endl;
    return 0;
}

Output:

Maximum rectangular Area is 12

Explanation:

Step 1: Understanding the Problem

You are given an array depicting a histogram's bar heights. The objective is to identify the maximum area of a rectangle that can be created within these bars.

Step 2: Initial Setup

To effectively calculate the maximum area of a rectangle, we will utilize a pair of arrays, known as left and right, to keep track of the limits for every bar. These limits play a crucial role in establishing the breadth of the most expansive rectangle achievable with each bar as the smallest element.

Step 3: Finding Left Limits

For each bar in the histogram, we need to find the nearest bar to its left that is shorter. This helps us understand how far the current bar can extend to the left while still maintaining the height of the rectangle.

• ✅ Traverse from Left to Right: Start from the first bar and move towards the last bar.
• ✅ Use a Stack: Maintain a stack to keep track of the indices of bars in increasing order of height.
• ✅ Update Left Array: For each bar, pop elements from the stack, until you find a bar that is shorter than the current bar. The left limit for the current bar is then the index of the top element in the stack (if the stack is not empty). If the stack is empty, it means there is no shorter bar to the left, so set the left limit accordingly.

Step 4: Finding Right Limits

For each bar, we also need to find the nearest bar to its right that is shorter. This helps us understand how far the current bar can extend to the right while still maintaining the height of the rectangle.

• ✅ Traverse from Right to Left: Start from the last bar and move towards the first bar.
• ✅ Use a Stack: Reuse the stack to keep track of the indices of bars in increasing order of height .
• ✅ Update Right Array: For each bar, pop elements from the stack, until you find a bar that is shorter than the current bar. The right limit for the current bar is then the index of the top element in the stack (if the stack is not empty). If the stack is empty, it means there is no shorter bar to the right, so set the correct limit accordingly.

Step 5: Calculating the Maximum Area

With the boundaries established on the left and right for every bar, we are able to compute the maximum area of a rectangle for each bar and monitor the overall maximum area.

• ✅ Establish Width: To find the width of the largest rectangle encompassing each bar, we compute the difference between the right and left boundaries minus one.
• ✅ Compute Area: The area is subsequently calculated by multiplying the height of the bar by this width.

Update the maximum area by comparing it with the currently discovered maximum area and making updates as necessary.

Example:

Consider a bar chart with the following heights: [6, 2, 5, 4, 5, 1, 6]:

Left Limits Calculation:

• ✅ For bar 6 (index 0): No bars to the left, so left limit is -1.
• ✅ For bar 2 (index 1): No bars shorter to the left, so left limit is -1.
• ✅ For bar 5 (index 2): Bar 2 is the nearest shorter bar to the left, so left limit is 1.
• ✅ For bar 4 (index 3): Bar 2 is the nearest shorter bar to the left, so left limit is 1.
• ✅ For bar 5 (index 4): Bar 4 is the nearest shorter bar to the left, so left limit is 3.
• ✅ For bar 1 (index 5): No bars shorter to the left, so left limit is -1.
• ✅ For bar 6 (index 6): Bar 1 is the nearest shorter bar to the left, so left limit is 5.

Right Limits Calculation:

• ✅ For bar 6 (index 6): No bars to the right, so right limit is 7.
• ✅ For bar 1 (index 5): No bars shorter to the right, so right limit is 7.
• ✅ For bar 5 (index 4): Bar 1 is the nearest shorter bar to the right, so right limit is 5.
• ✅ For bar 4 (index 3): Bar 1 is the nearest shorter bar to the right, so right limit is 5.
• ✅ For bar 5 (index 2): Bar 4 is the nearest shorter bar to the right, so right limit is 3.
• ✅ For bar 2 (index 1): Bar 1 is the nearest shorter bar to the right, so right limit is 5.
• ✅ For bar 6 (index 0): Bar 2 is the nearest shorter bar to the right, so right limit is 1.

Area Calculation:

• ✅ For bar 6 (index 0): Width is 1, Area is 6*1=6.
• ✅ For bar 2 (index 1): Width is 5, Area is 2*5=10.
• ✅ For bar 5 (index 2): Width is 1, Area is 5*1=5.
• ✅ For bar 4 (index 3): Width is 3, Area is 4*3=12.
• ✅ For bar 5 (index 4): Width is 1, Area is 5*1=5.
• ✅ For bar 1 (index 5): Width is 7, Area is 1*7=7.
• ✅ For bar 6 (index 6): Width is 1, Area is 6*1=6.

The largest Area found is 12.

Complexity analysis:

Time Complexity

Overall Time Complexity: O(n)

The computation of left limits is O(n) since each bar is pushed and popped from the stack exactly once.

Right Bounds Computation: O(n) due to identical rationale.

Area Calculation: Operates in linear time complexity O(n) since it requires traversing the bars only once.

Space Complexity

Overall Space Complexity: O(n)

Auxiliary Arrays: The time complexity for creating the left and right arrays is O(n).

Stack: In the worst-case scenario, the time complexity is O(n) where the stack has the capacity to store all bar indices.

Therefore, the Dynamic Programming method has a time complexity of O(n) and a spatial complexity of O(n).