> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/stack/largest-rectangle-in-histogram.md).

# Largest Rectangle in Histogram

## Question ([LC.84](https://leetcode.com/problems/largest-rectangle-in-histogram/))

> The only input is `heights`, an array of integers, representing the heights of bars. Each bar has a unit width of `1`. The question is to find the area of the largest rectangle in the histogram.

## Examples 

```
I: heights = [2, 1, 5, 6, 2, 3]
O: 10 (2 x 5)

I: heights = [2, 4]
O: 4 (2 x 2, 1 x 4)
```

## Initial Approach 

The brute force idea is to enumerate every possible intervals. Then compute the largest rectangle in each interval. The time complexity is O(n^2 \* compute the area). 

## Code 

```java
public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    
    int maxRec = 0;
    for (int i = 0; i < heights.length; i++) {
        int lowestHeight = 10000;
        for (int j = i; j < heights.length; j++) {
            int width = j - i + 1;
            lowestHeight = Math.min(lowestHeight, heights[j]);
            maxRec = Math.max(maxRec, width * lowestHeight);
        }
    }
    return maxRec;
}
```

This approach times out at 90/98 test cases when n is around 9000.&#x20;

## Better Approach&#x20;

1. Bring down to O(nlogn) with sorting then find largest with a greedy approach&#x20;
   1. Index ordering is important so cannot just sort by value&#x20;
2. Bring down to O(nlogn) with D\&C&#x20;
   1. Divide with O(n) and merge with O(1)
3. Bring down to O(n) with dynamic programming&#x20;
   1. Interval will have O(n^2) states
   2. Prefix is not enough for a state i to get an optimal answer&#x20;

TODO: D\&C code&#x20;

Stack overflow error when n = 60000 and the recursion depth is 30000.&#x20;

95/98 test cases passed&#x20;

## Monotonic Stack&#x20;

It turns out this is a classic use case for the monotonic stack - finding the next smaller / greater element in a list.&#x20;

In order to do that, we have to reframe the answer to this question a bit. The brute force approach is fixing on the width (interval) to find the minimum height. Alternatively, fixing on the height (value) to find the maximum width is also an option to enumerate all the rectangles.

In pseudo code&#x20;

```
def findLargestRectangleArea(heights):
    leftBounds = findLeftBounds(heights)  # return a list of left bounds for each index
    rightBounds = findRightBounds(heights)  # return a list of right bounds for each index
    maxArea = 0
    for i from 0 to n-1:
        height = heights[i]  # fixed
        width = rightBounds[i] - leftBounds[i] + 1  # query 
        area = width * height 
        maxArea = max(maxArea, area)
    return maxArea
```

## Code

```java
public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }

    int[] leftBounds = findLeftBounds(heights);
    int[] rightBounds = findRightBounds(heights);

    int maxArea = 0;
    for (int i = 0; i < heights.length; i++) {
        int height = heights[i];
        int width = rightBounds[i] - leftBounds[i] - 1;
        int area = width * height;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

/*
The correct math for width is rightBound[i] - leftBound[i] - 1

i.e.,  LBound   box box    RBound 

left_bounds should be initialized to -1 
right_bounds should be initialized to heights.length 
*/
private int[] findLeftBounds(int[] heights) {
    int[] leftBounds = new int[heights.length];

    for (int i = 0; i < heights.length; i++) {
        leftBounds[i] = -1;
    }

    // store index 
    Stack<Integer> incStack = new Stack<>();

    for (int i = 0; i < heights.length; i++) {
        while (!incStack.isEmpty() && heights[incStack.peek()] > heights[i]) {
            incStack.pop();
        }
        // set left bound 
        // left is a decreasing element 
        if (!incStack.isEmpty()) {
            leftBounds[i] = incStack.peek();
        }
        incStack.push(i);
    }
    return leftBounds;
}

private int[] findRightBounds(int[] heights) {
    int[] rightBounds = new int[heights.length];
    
    for (int i = 0; i < heights.length; i++) {
        rightBounds[i] = heights.length;
    }

    // store index 
    Stack<Integer> incStack = new Stack<>();

    for (int i = 0; i < heights.length; i++) {
        // pop because of a decreasing element 
        // the decreasing element is the right bound 
        while (!incStack.isEmpty() && heights[incStack.peek()] > heights[i]) {
            int popIndex = incStack.pop();
            rightBounds[popIndex] = i;
        }
        incStack.push(i);
    }
    return rightBounds;
}
```

O(n) time and space&#x20;

215ms test cases are large for this question&#x20;

## Reference&#x20;

InterviewBit - [Largest Rectangle in Histogram](https://www.interviewbit.com/blog/largest-rectangle-in-histogram/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-1/basic_data_structure/stack/largest-rectangle-in-histogram.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.