Largest Rectangle in Histogram - Java Solution

1. Introduction

In this post, we'll be exploring a solution to the "Largest Rectangle in Histogram" problem, a classic problem in computational geometry. The challenge is to find the largest rectangular area that can be formed within a given histogram, where each bar has a width of 1 and a given height.

Problem

Given an array of integers heights representing the height of bars in a histogram, the task is to find the area of the largest rectangle that can be formed within the histogram.

2. Solution Steps

1. Use a stack to keep track of the indices of the bars.

2. Iterate through each bar in the histogram:

- While the current bar is smaller than the bar at the top of the stack, calculate the area of the rectangle with the height of the bar at the top of the stack.

- Update the maximum area if necessary.

- Push the current bar's index onto the stack.

3. After the array is processed, pop all bars from the stack and calculate the area using the remaining bars.

4. The largest area calculated in these steps is the solution.

3. Code Program

import java.util.Stack;

public class LargestRectangleInHistogram {
    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(heights)); // Test the function
    }

    // Function to find the largest rectangle in the 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++) {
            int h = (i == n ? 0 : heights[i]);
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - 1 - stack.peek();
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }
}

Output:

10

Explanation:

1. largestRectangleArea: This function calculates the largest rectangular area in a histogram.

2. A Stack is used to keep track of bar indices. The stack helps in finding the next smaller bar for a given bar.

3. The algorithm iterates through each bar and calculates the area of rectangles with the current bar as the smallest height.

4. When a smaller bar is encountered, it calculates the potential maximum areas with the bars in the stack and updates the maxArea accordingly.

5. After processing all bars, the largest area found is returned.

6. This method efficiently computes the largest rectangle area using a stack, with a time complexity of O(n).