Largest Rectangle in Histogram

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.

For example:

heights = [2,1,5,6,2,3] Output: 10 Explanation: The largest rectangle is of height 5 and width 2, so the area is 10

heights = [2,4] Output: 4 Explanation: The largest rectangle is of height 4 and width 1, so the area is 4

Constraints:

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

## Largest Rectangle in Histogram

This problem asks us to find the largest rectangular area in a histogram represented by an array of heights, where each bar has a width of 1.

### 1. Brute Force Solution

We can iterate through each bar and consider it as the minimum height of a rectangle. Then, we expand to the left and right as long as the heights are greater than or equal to the current bar's height. This will give us the width of the rectangle, and we can calculate the area. We keep track of the maximum area found so far.

```python
def largest_rectangle_brute_force(heights):
    max_area = 0
    n = len(heights)

    for i in range(n):
        height = heights[i]
        width = 1

        # Expand to the left
        left = i - 1
        while left >= 0 and heights[left] >= height:
            width += 1
            left -= 1

        # Expand to the right
        right = i + 1
        while right < n and heights[right] >= height:
            width += 1
            right += 1

        area = height * width
        max_area = max(max_area, area)

    return max_area

# Example usage:
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_brute_force(heights))  # Output: 10

2. Optimal Solution: Using Stack

A more efficient solution involves using a stack to keep track of the indices of increasing heights. When we encounter a height that is smaller than the height at the top of the stack, it means we have found the right boundary for the rectangle with the height at the top of the stack as the minimum height. We can then calculate the area and update the maximum area.

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    n = len(heights)
    i = 0

    while i < n or stack:
        if not stack or (i < n and heights[i] >= heights[stack[-1]]):
            stack.append(i)
            i += 1
        else:
            top = stack.pop()
            area = heights[top] * (i if not stack else i - stack[-1] - 1)
            max_area = max(max_area, area)

    return max_area

# Example usage:
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))  # Output: 10

3. Big(O) Runtime Analysis

• Brute Force: The outer loop iterates n times, and the inner loops (expanding left and right) can potentially iterate up to n times in the worst case. Therefore, the time complexity is O(n^2).
• Optimal (Stack): Each element is pushed onto the stack and popped off the stack at most once. Therefore, the time complexity is O(n).

4. Big(O) Space Usage Analysis

• Brute Force: The brute force solution uses a constant amount of extra space. Therefore, the space complexity is O(1).
• Optimal (Stack): The stack can potentially store all the indices in the worst case (when the heights are in increasing order). Therefore, the space complexity is O(n).

5. Edge Cases

• Empty Input: If the input array is empty, the largest area is 0. The provided code handles this case because the loops won't execute.
• All Bars with Same Height: If all bars have the same height, the largest area is the height multiplied by the number of bars.
• Input with Zero Heights: If the input contains zero heights, the algorithm should still work correctly. Zero heights will simply limit the expansion of rectangles.
• Large Heights: If the heights are very large, we need to be careful about potential integer overflow when calculating the area. Using long or appropriate data types may be necessary depending on the language.