Largest rectangle in a histogram

Problem Overview

The problem "Largest Rectangle in Histogram" on LeetCode is a challenging yet classic problem in the field of data structures, particularly focusing on stacks. The task is to find the largest rectangular area possible in a histogram bar chart, where the width of each bar is 1.

The problem can be summarized as follows:

You are given an array heights representing the heights of bars in a histogram. The task is to calculate the area of the largest rectangle that can be formed within the bounds of these histogram bars.

Understanding the Problem

To understand the problem clearly, let's consider a histogram where the heights are given as [2, 1, 5, 6, 2, 3]. The histogram will look somewhat like:

        _ 
       |_|
    _  |_|
   |_||_||_ 
   |_||_||_|

Our goal is to find the largest rectangle that can be formed under the histogram bars. In the above example, the largest rectangle has an area of 10, which spans from the third to the fourth bars with heights [5, 6].

The challenge lies in the fact that while a brute-force approach could be considered (evaluating each possible rectangle), it would be inefficient, especially for large input sizes.

Key DSA Concepts and Theory

The main data structures used in solving this problem efficiently are:

Stack

• Stack is a linear data structure following the Last In First Out (LIFO) principle. It suits the needs of this problem because it allows us to efficiently find and maintain the indices of histogram bars in a way that helps in calculating areas dynamically without recalculating for every possibility.

Histogram Problem and Spans

• Solving the largest rectangle in a histogram involves calculating the area of rectangles that span multiple or single bars and figuring out which of these has the maximum area.

• The key observation is that if a bar at index i is lower than the bar at i-1, then bar i-1 cannot be a part of any larger width rectangle ending at or beyond i.

Solution Approach

An effective approach to solving this problem involves the use of a stack to maintain the indices of the histogram bars.

Steps:

1. Initialization:

   • Initialize an empty stack to store indices of bars and a variable maxArea to track the maximum area found.

2. Iterate through the histogram:

   • For each bar at height heights[i], use the stack to find the largest area rectangle possible with the current top of the stack as the smallest (or limiting) height.

   • If the stack is not empty and the current bar is lower than the bar represented by the index on top of the stack:

     • Pop the stack and calculate the area using the popped index as the smallest height.
     • Use the difference between the current index and the index of the new top of the stack after popping as the width of the area.

3. Calculate and Update the Maximum Area:

   • Continue this process until the stack is empty. This ensures that all possible rectangles are checked.

4. Handle Remaining Bars on Stack:

   • If any bars remain on the stack after the iteration, they need to be processed similarly to assess any possible largest rectangle ending at the array's end.

5. Return the maxArea Calculated.

Here is the implementation in C++ and Java:

C++ Code:

#include <vector>
#include <stack>
#include <algorithm>

class Solution {
public:
    int largestRectangleArea(std::vector<int>& heights) {
        std::stack<int> indices;
        int maxArea = 0;
        int n = heights.size();

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

        while (!indices.empty()) {
            int h = heights[indices.top()];
            indices.pop();
            int width = indices.empty() ? n : n - indices.top() - 1;
            maxArea = std::max(maxArea, h * width);
        }

        return maxArea;
    }
};

Java Code:

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> indices = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

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

        while (!indices.isEmpty()) {
            int h = heights[indices.pop()];
            int width = indices.isEmpty() ? n : n - indices.peek() - 1;
            maxArea = Math.max(maxArea, h * width);
        }

        return maxArea;
    }
}

Time and Space Complexity Analysis

• Time Complexity: The algorithm has a time complexity of O(n), where n is the number of bars in the histogram. This is because each bar is pushed and popped from the stack at most once.

• Space Complexity: The space complexity is O(n) due to the allocation used by the stack to store the indices.

Common Mistakes to Avoid

1. Handling of Remaining Bars on Stack: Ensure that after the first iteration through the array, you handle all remaining bars on the stack, as they can form potential largest rectangles when used as the smallest height.

2. Width Calculation: Pay careful attention to the calculation of rectangular width after popping from the stack. Using index differences incorrectly is a common source of errors.

Similar Problems on LeetCode

1. Trapping Rain Water (LeetCode #42)
2. Maximal Rectangle (LeetCode #85)
3. Circular Array Loop (LeetCode #457)

Additional Resources and References

1. Stack Data Structure
2. LeetCode Problem Solution Discussions
3. Visualizing Histogram Algorithms using GeeksforGeeks

Understanding how to utilize stacks effectively for problems like the largest rectangle in a histogram is crucial for optimizing these solutions. Practice with similar problems to improve understanding and efficiency.