Table of contents

Largest Rectangular Area in Histogram

Given an array of integers where each element represents the height of a histogram's bar, find the area of the largest rectangle that can be formed in the histogram.

Input/Output Examples

plaintext
Example 1:
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10
Explanation: The largest rectangle has an area of 10 units and is formed by the bars at indices 2 and 3 (heights [5, 6]).

Example 2:
Input: heights = [2, 4]
Output: 4
Explanation: The largest rectangle has an area of 4 units and is formed by the bar at index 1 (height 4).

Approach to Find the Largest Rectangular Area in a Histogram

  1. Use a Stack to Track Indices:
    • To efficiently find the largest rectangle, we can use a stack to keep track of the indices of the histogram bars in ascending order.
  2. For Each Bar:
    • If the current bar is higher than or equal to the bar at the top of the stack, push its index onto the stack.
    • If the current bar is lower, pop from the stack, calculate the area with the popped bar as the smallest (or limiting) height, and compare it with the maximum area found so far.
  3. Handle Remaining Bars:
    • After traversing all bars, pop the remaining bars from the stack and calculate areas similarly.

C++ Program to Find the Largest Rectangular Area in a Histogram

cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// Function to find the largest rectangular area in a histogram
int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int maxArea = 0;
    int n = heights.size();

    for (int i = 0; i < n; i++) {
        // While the current bar is lower than the bar at the top of the stack
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()];
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, h * width);
        }
        st.push(i);
    }

    // Calculate the area for the remaining bars in the stack
    while (!st.empty()) {
        int h = heights[st.top()];
        st.pop();
        int width = st.empty() ? n : n - st.top() - 1;
        maxArea = max(maxArea, h * width);
    }

    return maxArea;
}

int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "Largest Rectangle Area: " << largestRectangleArea(heights) << endl;
    return 0;
}

Java Program to Find the Largest Rectangular Area in a Histogram

java
import java.util.Stack;

public class LargestRectangleHistogram {

    // Function to find the largest rectangular area in a histogram
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int h = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * width);
            }
            stack.push(i);
        }

        // Calculate the area for the remaining bars in the stack
        while (!stack.isEmpty()) {
            int h = heights[stack.pop()];
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, h * width);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println("Largest Rectangle Area: " + largestRectangleArea(heights));
    }
}

Python Program to Find the Largest Rectangular Area in a Histogram

python
# Function to find the largest rectangular area in a histogram
def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    n = len(heights)

    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * width)
        stack.append(i)

    # Calculate the area for the remaining bars in the stack
    while stack:
        h = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, h * width)

    return max_area

# Example usage
if __name__ == "__main__":
    heights = [2, 1, 5, 6, 2, 3]
    print("Largest Rectangle Area:", largest_rectangle_area(heights))
  • Time Complexity: O(n), where n is the number of bars in the histogram. Each bar is pushed and popped from the stack at most once.
  • Space Complexity: O(n), where n is the number of bars. This space is required for the stack.

DSA

Related Articles