Largest Rectangle in Histogram Problem using Stack

Largest Rectangle in Histogram Problem using Stack

The Largest Rectangle in Histogram problem involves finding the largest rectangular area that can be formed in a histogram represented by an array of heights. This can be efficiently solved using a stack to manage the indices of the histogram bars.

---

Step-by-Step Process

Consider a histogram represented by the following array of heights:

[2, 1, 5, 6, 2, 3]

To find the largest rectangular area in this histogram using a stack, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of the indices of the histogram bars.
2. Traverse the Array: Iterate through each bar in the histogram.
3. Push Indices onto the Stack: If the current bar is higher than the bar at the index on the top of the stack, push the current index onto the stack.
4. Calculate Areas: If the current bar is lower than the bar at the index on the top of the stack, pop the stack and calculate the area with the popped bar as the smallest (or minimum height) bar. Continue popping from the stack and calculating areas until the current bar is higher than the bar at the index on the top of the stack.
5. Handle Remaining Bars: After processing all bars, pop the remaining bars from the stack and calculate the area with each popped bar as the smallest bar.
6. Keep Track of the Maximum Area: Throughout the process, keep track of the maximum area found.

After performing these steps, the largest rectangular area in the histogram will be found.

Input: [2, 1, 5, 6, 2, 3]
Output: 10

---

Pseudo Code

Function largest_rectangle_area(heights):
    # Initialize an empty stack
    stack = []
    max_area = 0
    index = 0
    # Traverse the array
    While index < len(heights):
        # Push the current index onto the stack if the stack is empty or the current height is greater than the height at the stack's top index
        If not stack or heights[index] >= heights[stack[-1]]:
            stack.append(index)
            index += 1
        Else:
            # Pop the top index from the stack
            top_of_stack = stack.pop()
            # Calculate the area with the popped index as the smallest bar
            area = (heights[top_of_stack] * ((index - stack[-1] - 1) if stack else index))
            # Update max_area if the calculated area is greater
            max_area = max(max_area, area)
    # Calculate area for the remaining bars in the stack
    While stack:
        top_of_stack = stack.pop()
        area = (heights[top_of_stack] * ((index - stack[-1] - 1) if stack else index))
        max_area = max(max_area, area)
    Return max_area

---

Python Program to Solve the Largest Rectangle in Histogram Problem using Stack

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

    def traverse(self):
        for item in reversed(self.stack):
            print(item, end=" -> ")
        print("None")

# Function to find the largest rectangular area in a histogram
def largest_rectangle_area(heights):
    stack = Stack()
    max_area = 0
    index = 0
    while index < len(heights):
        if stack.is_empty() or heights[index] >= heights[stack.peek()]:
            stack.push(index)
            index += 1
        else:
            top_of_stack = stack.pop()
            area = (heights[top_of_stack] * ((index - stack.peek() - 1) if not stack.is_empty() else index))
            max_area = max(max_area, area)
    while not stack.is_empty():
        top_of_stack = stack.pop()
        area = (heights[top_of_stack] * ((index - stack.peek() - 1) if not stack.is_empty() else index))
        max_area = max(max_area, area)
    return max_area

# Example usage:
histogram = [2, 1, 5, 6, 2, 3]
print(f"Histogram: {histogram}")  # Output: Histogram: [2, 1, 5, 6, 2, 3]
max_area = largest_rectangle_area(histogram)
print(f"Largest rectangle area: {max_area}")  # Output: Largest rectangle area: 10

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The largest_rectangle_area function uses the stack to find the largest rectangular area in a histogram by processing each bar, comparing it with the stack's top element, and updating the maximum area accordingly.