Largest Rectangle in Histogram - Time Complexity: O(n) - Java Solution

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 10⁵
0 <= heights[i] <= 10⁴

Understanding the Problem

The core challenge of this problem is to find the largest rectangular area that can be formed within the histogram. This problem is significant in various fields such as computer graphics, data visualization, and computational geometry. A common pitfall is to attempt a brute-force solution, which would be inefficient for large inputs.

Approach

To solve this problem, we can use a stack-based approach which allows us to efficiently calculate the largest rectangle. The naive solution would involve checking all possible rectangles, which would be too slow (O(n^2) time complexity). Instead, we can use a stack to keep track of the indices of the histogram bars.

Optimized Solution

The optimized solution involves using a stack to store the indices of the histogram bars. We iterate through the bars, and for each bar, we maintain the stack such that the heights of the bars corresponding to the indices in the stack are in non-decreasing order. When we encounter a bar that is shorter than the bar at the index stored at the top of the stack, we pop the stack and calculate the area of the rectangle with the popped bar as the smallest (or minimum height) bar. This ensures that we calculate the maximum possible area for each bar efficiently.

Algorithm

Initialize an empty stack and a variable to store the maximum area.
Iterate through each bar in the histogram.
For each bar, if the stack is empty or the current bar is taller than the bar at the index stored at the top of the stack, push the current index onto the stack.
If the current bar is shorter, pop the stack and calculate the area of the rectangle with the popped bar as the smallest bar. Update the maximum area if the calculated area is larger.
After iterating through all bars, pop the remaining bars in the stack and calculate the area for each, updating the maximum area as needed.

Code Implementation

import java.util.Stack;

public class LargestRectangleInHistogram {
    public int largestRectangleArea(int[] heights) {
        // Initialize a stack to store indices of histogram bars
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            // Get the current height or 0 if we are at the end
            int currentHeight = (i == n) ? 0 : heights[i];

            // While the stack is not empty and the current height is less than the height of the bar at the top of the stack
            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                // Pop the top of the stack and calculate the area
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }

            // Push the current index onto the stack
            stack.push(i);
        }

        return maxArea;
    }

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

        int[] heights2 = {2, 4};
        System.out.println("Largest Rectangle Area: " + solution.largestRectangleArea(heights2)); // Output: 4
    }
}

Complexity Analysis

The time complexity of this approach is O(n) because each bar is pushed and popped from the stack at most once. The space complexity is O(n) due to the stack used to store the indices.

Edge Cases

Some potential edge cases include:

All bars have the same height.
Bars are in increasing or decreasing order.
Only one bar in the histogram.

Each of these cases is handled by the stack-based approach, ensuring that the maximum area is calculated correctly.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with a few bars.
Cases with all bars of the same height.
Cases with bars in increasing or decreasing order.
Edge cases with the minimum and maximum number of bars.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem constraints and requirements.
Consider both naive and optimized solutions.
Use data structures like stacks to manage and process data efficiently.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the "Largest Rectangle in Histogram" problem is crucial for developing efficient algorithms. By using a stack-based approach, we can achieve an optimal solution with a time complexity of O(n). Practicing such problems helps in honing problem-solving skills and understanding the application of data structures.