Largest Rectangle In Histogram - Leetcode Solution

Problem Statement:

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Example 1:

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

Example 2:

Input: heights = [2,4] Output: 4

Solution:

We can solve this problem by using the concept of stack. The intuition is to traverse through the heights array and for each height, we want to find the maximum area rectangle with this height as the smallest bar. To do that, we will use a stack to maintain left and right boundaries of the rectangle.

1. Initialize an empty stack and a variable called max_area to store the maximum area. Then iterate through the input array, heights.

2. For each height i, if the stack is empty or the current height is greater than or equal to the height at the top of the stack, push the current index i onto the stack.

3. If the current height is less than the height at the top of the stack, pop the top of the stack and calculate the area of the rectangle with the popped height as the smallest bar.

4. The width of the rectangle is the current index i minus the index at the top of the stack minus 1 (since we popped the top of the stack).

5. The height of the rectangle is the popped height.

6. Calculate the area of the rectangle by multiplying the height by the width.

7. Update the max_area variable if the area of the current rectangle is greater than the current max_area.

8. Repeat steps 3-7 until the current height is greater than or equal to the height at the top of the stack.

9. Push the current index i onto the stack.

10. After iterating through the entire input array, repeat steps 3-7 for each remaining element on the stack until the stack is empty.

11. Return max_area.

Code:

1