LC84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

lc pic

Brute Force

We will iterate all n^2 possible start and end pairs. Then for each start and end pair, we need to find the smallest height; It will be the limiting height. (It’s like we are as tall as our shortest member). The area will be (end – start + 1) * minHeight

<br />class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        //bf
        if (heights.empty())
            return 0;
        int maxArea = -1;
        for(int i = 0; i < heights.size(); i ++){
            for(int j = i; j < heights.size(); j ++){
                int minHeight = heights[i];
                for(int k = i; k <= j ; k ++){
                    minHeight = min(minHeight, heights[k]);
                }
                maxArea = max(maxArea, (j - i + 1)* minHeight);
            }
        }
        return maxArea;
    }
};

This algorithm looks O(n^3) and it times out.

Pick a column and expand.

One of the cost in the last algo is we need to find min for every start/end pair. What if we just pick a column and start expand to both side to find the max? We have n column and each expansion will at most take n steps. So that’s O(n^2).

For each rectangle, there will be at least one column in the rectangle that’s equal to its height, aka the shortest column in the rectangle. Let’s assume the shortest column is at index i. All other columns in the rectangle will have equal or higher heights.
If we can determine the index of the left most column whose height is higher the the shortest column in the rectangle, l, and the index of the right most column whose height is higher or equal to the shortest column, r, the area would be (r – l + 1)* heights[i].


class Solution { public: int largestRectangleArea(vector<int>& heights) { if(heights.empty()) return 0; int maxArea = 0; vector<int> leftHeightIdx(heights.size(), 0); //first left s.t h[i] > h[leftHeight[i]] vector<int> rightHeightIdx(heights.size(), 0); //rightmost idx where h[i] > h[rightHeight[i]] leftHeightIdx[0] = 0; rightHeightIdx[heights.size() - 1] = heights.size() - 1; for(int i = 1; i < heights.size(); i ++ ){ int ptr = i; //if height[i] is the shortest in rec, how far left can we go while( ptr > 0 && heights[i] <= heights[ptr - 1] ) ptr --; leftHeightIdx[i] = ptr; } for(int i = heights.size() - 2; i >= 0; i --){ int ptr = i; while(ptr < heights.size() - 1 && heights[i] <= heights[ptr + 1]) ptr ++; rightHeightIdx[i] = ptr; } //for(int i = 0; i < heights.size(); i ++){ // cout<<i <<"idx left:" << leftHeightIdx[i] <<" right: "<<rightHeightIdx[i]<<'\n'; //} for(int i = 0; i < heights.size(); i++){ int currArea = (rightHeightIdx[i] - leftHeightIdx[i] + 1) * heights[i]; maxArea = max(maxArea, currArea); } return maxArea; } };

O(n)

We are repeating a lot of works: For each i, we expand left and right to find the leftmost and rightmost index whose height is >= heights[i].

But we can save some work; In the previous algorithm, we are repeatedly calculating the left and right boundary of a rect bounded by heights[i].

At i, we already know the left boundary of i – 1. So if heights[i] <= height[i – 1], then left boundary of i will be at least leftHeightIdx[i – 1]. It is also possible that we need to go back even further: let l = leftHeightIdx[i – 1]. if h[l] >= h[i], then we need to expand the left boundary further until h[l] > h[i].

Minor change

To make use of the left one before current index, we need to change leftHeightIdx[i] to store the first idx that’s not in the boundary.

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty())
            return 0;
        int maxArea = 0;
        vector<int> leftHeightIdx(heights.size(), 0);  //first left s.t h[i] > h[leftHeight[i]]
        vector<int> rightHeightIdx(heights.size(), 0); //rightmost idx where h[i] > h[rightHeight[i]]
        leftHeightIdx[0] = -1;
        rightHeightIdx[heights.size() - 1] = heights.size();

        for(int i = 1; i < heights.size(); i ++ ){
            int ptr = i - 1;
            while(ptr >= 0 && heights[i] <= heights[ptr])
                ptr = leftHeightIdx[ptr];

            leftHeightIdx[i] = ptr;
        }

        for(int i = heights.size() - 2; i >= 0; i --){
            int ptr = i + 1;
            while(ptr < heights.size() && heights[i] <= heights[ptr]){
                ptr = rightHeightIdx[ptr];
            }
            rightHeightIdx[i] = ptr;
        }
        //for(int i = 0; i < heights.size(); i ++){
        //    cout<<i <<"idx left:" << leftHeightIdx[i] <<" right: "<<rightHeightIdx[i]<<'\n';
        //}
        for(int i = 0; i < heights.size(); i++){
            int currArea = (rightHeightIdx[i] - leftHeightIdx[i] - 1) * heights[i];
            maxArea = max(maxArea, currArea);
        }


        return maxArea;
    }

};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax