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.

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^5
• 0 <= heights[i] <= 10^4

# Largest Rectangle in Histogram

This problem asks us to find the largest rectangular area that can be formed within a histogram, given an array of heights where each bar has a width of 1.

## 1. Brute Force Solution

A naive approach would be to consider every possible pair of bars in the histogram and calculate the area of the rectangle they define. We can iterate through all possible start and end indices of the rectangle, determine the minimum height within that range, and then calculate the area as `(end - start + 1) * min_height`.  The maximum of these areas will be the answer.

```python
def largest_rectangle_brute_force(heights):
    max_area = 0
    n = len(heights)
    for i in range(n):
        for j in range(i, n):
            min_height = min(heights[i:j+1])
            area = (j - i + 1) * min_height
            max_area = max(max_area, area)
    return max_area

# Example usage
heights = [2, 1, 5, 6, 2, 3]
print(f"Largest Rectangle Area (Brute Force): {largest_rectangle_brute_force(heights)}") # Output: 10

2. Optimal Solution (Using Stack)

A more efficient approach involves using a stack to keep track of increasing bar heights. The stack helps us determine the left and right boundaries for each bar, allowing us to calculate the area it can contribute to the largest rectangle. Here's how it works:

1. Initialize an empty stack.
2. Iterate through the heights array.
3. If the current bar is taller than the bar at the top of the stack, push its index onto the stack.
4. If the current bar is shorter than the bar at the top of the stack, pop bars from the stack until we find a bar that is shorter or the stack is empty.
5. For each popped bar, calculate its area using the current index as the right boundary and the next element on the stack (if any) as the left boundary.

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    n = len(heights)
    
    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack:
        height = heights[stack.pop()]
        width = n if not stack else n - stack[-1] - 1
        max_area = max(max_area, height * width)

    return max_area

# Example usage
heights = [2, 1, 5, 6, 2, 3]
print(f"Largest Rectangle Area (Stack): {largest_rectangle_area(heights)}") # Output: 10

3. Big(O) Time Complexity Analysis

• Brute Force: The brute force solution has a time complexity of O(n^2), where n is the number of bars in the histogram. This is because we have nested loops to consider every possible sub-array. The min operation inside the inner loop contributes O(n) in the worst case, making the complexity closer to O(n^3), although in practice it behaves more like O(n^2).
• Stack Approach: The stack-based solution has a time complexity of O(n). Each bar is pushed onto the stack and popped off the stack at most once. Thus, the while loop does not run n times for every element. The while loop runs a total of n times maximum in the entire function. Therefore, the operations are proportional to the number of bars, leading to O(n).

4. Big(O) Space Complexity Analysis

• Brute Force: The brute force solution has a space complexity of O(1) as it uses a constant amount of extra space.
• Stack Approach: The stack-based solution has a space complexity of O(n) in the worst case, where n is the number of bars in the histogram. This occurs when the heights are continuously increasing, and all the indices are pushed onto the stack.

5. Edge Cases

• Empty Histogram: If the input heights array is empty, the largest area is 0. This is handled correctly by both the brute-force and stack-based solutions.
• Histogram with One Bar: If the histogram has only one bar, the largest area is simply the height of that bar. Both solutions will handle this case correctly.
• Histogram with All Zero Heights: If all heights are zero, the largest area is 0. The solutions handle this correctly.
• Histogram with Decreasing Heights: A histogram with monotonically decreasing heights will be correctly processed by the stack-based solution, as the stack will efficiently determine the boundaries for each bar.
• Large Input: The stack-based solution is much more efficient for large inputs due to its O(n) time complexity, while the brute force can be slow because of its O(n^2) time complexity.