Largest Rectangle in Histogram - Python Solution

1. Introduction

The "Largest Rectangle in Histogram" problem is a classic in computational geometry and stack-based algorithms. It involves finding the largest rectangle that can fit within a histogram given an array representing the heights of the bars. This problem tests understanding of data structures and the ability to apply them to complex computational problems.

Problem

Given an array of integers heights representing the heights of histogram bars where the width of each bar is 1, the task is to return the area of the largest rectangle that can be formed within the histogram.

2. Solution Steps

1. Initialize a stack to keep track of the indices of the histogram bars.

2. Iterate through each bar in the histogram.

3. While the current bar is shorter than the bar at the top of the stack, calculate the area of the rectangle with the stack's top bar as the smallest bar.

4. Update the maximum area found so far.

5. Push the current bar onto the stack.

6. After the final bar, pop all remaining bars from the stack, calculating the area for each.

7. Return the maximum area found.

3. Code Program

def largestRectangleArea(heights):
    stack = []
    max_area = 0

    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

# Example Usage
print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

Output:

10

Explanation:

1. Stack Implementation: Uses a stack to keep track of bar indices for potential largest rectangles.

2. Iterative Approach: Iterates through each bar, using the stack to calculate areas.

3. Area Calculation: Calculates the area of rectangles, considering the current bar as the ending bar.

4. Max Area Update: Continuously updates the maximum area found during the iteration.

5. Post-Iteration Cleanup: Handles remaining bars in the stack after iterating through all bars.

6. Efficiency: The algorithm efficiently calculates the largest area with O(n) time complexity.

7. Applicability: Demonstrates a practical use case for stack data structures in solving geometric problems.