Contents

Largest Rectangle In Histogram

Hey there! This is my first technical post. I’ll be discussing the “Largest Rectangle in Histogram” problem. This problem used to trouble me a lot. But it is an interesting one!

Problem
You are given an array representing the heights of the bars in a histogram. You are supposed to find the largest rectangle that can be formed using the bars in the histogram.

You can try it out on your own on binarysearch.com: Problem Link

Example:

If you are given the array : arr = [2, 7, 8, 4, 6], the histogram will look like this.

/posts/largest_rectangle_in_histogram/Original_Problem.jpg
Diagram

Clearly, the solution to the problem will be the shaded rectangle.

/posts/largest_rectangle_in_histogram/Solution.jpg
Diagram

We will use this input as an example throughout the post.

On careful observation, we can notice that the height of the largest rectangle will always be the height of one of the bars present in the input array. This actually helps us to develop a naive solution.

Key Idea
We can simply go on extending every bar bib_i to its left and right until we come across another bar which is shorter than it.

Here is a C++ implementation for the same:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int solve(vector<int>& arr) {
    int n = arr.size(), max_area = 0, lo, hi, width, height;

    for (int i = 0; i < n; i++) {
        height = arr[i];
        lo = hi = i;
        while (lo >= 0 && arr[lo] >= height) lo--; // expand bar to left
        while (hi < n && arr[hi] >= height) hi++;  // expand bar to right
        width = hi - lo - 1;                       // calculate width
        max_area = max(max_area, width * height);  // update global ans
    }
    return max_area;
}

The time complexity of this code is O(n2)O(n^{2}) which is too slow.

  • In the Naive approach, we essentially try to extend a bar to the left and right directions until we come across a bar which is smaller than it. So in essence, we only care about the location of the first bar which is smaller to the left and the first bar which is smaller to the right. Now, what if we had a way to precompute the locations of the next smaller bar for every bar, for both its left and right side? This will allow us to get rid of the two inner while loops.

  • It turns out that you can perform this precomputation in O(n)O(n) time using stack. This is actually a variant of the classic Next Greater to the Right (NGR) problem. In this case, we are concerned with the location of the next smaller elements. The NGR problem can be solved using monostack.

  • You are expected to return an vector/array of size nn such that : ans[i] = Index of the next smaller element(bar) to the left of arr[i]

  • For our convenience, we assume that there is an imaginary zero height bar at index -1 as shown in the below figure. Consequently, for a bar bib_{i} which has no smaller bar to its left, we set ans[i] = -1, indicating that the imaginary zero height bar is the next smaller to its left. This explains the initialization of the ans vector to -1 when its declared. We make a similar assumption for the Nearest Smaller to the Right (NSR) problem. In NSR, the imaginary zero height bar is at index n.

/posts/largest_rectangle_in_histogram/org_with_indices.png
Note how we have a zero height bar at indices -1 and 5 respectively.
  • The solution for Next Smaller to the Left ( NSL ) problem for the histogram in our example can be given as: ans[i] = [-1, 0, 1, 0, 3]. The figure below gives more insight on how we obtain the solution. The arrows point to the next smaller bar to the left for every bar.
/posts/largest_rectangle_in_histogram/NSL.png
Figure depicting NSL of every bar height.
  • Similarly we can build an answer for Next Smaller to the Right ( NSR ) problem. ans[i] = [5, 3, 3, 5, 5 ].
/posts/largest_rectangle_in_histogram/NSR.png
Figure depicting NSR of every bar height.

Here’s an implementation for Nearest Smaller to the left ( NSL ) problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
vector<int> NSL(vector<int>& arr) {
    /*
    Returns a vector as a solution for Nearest Smaller to the Left Problem
    */
    int n = arr.size();
    stack<int> stk;

    vector<int> ans(n, -1);
    for (int i = 0; i < n; i++){
        while (!stk.empty() && arr[stk.top()] >= arr[i]){
            stk.pop();
        }
        if (!stk.empty()) ans[i] = stk.top();
        stk.push(i);
    }
    return ans;
}

Implementation for NSR:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
vector<int> NSR(vector<int>& arr){
    /*
    Returns a vector as a solution for Nearest Smaller to the Right Problem
    */
   int n = arr.size();
    stack<int> stk;
    vector<int> ans(n, n);

    for (int i = n - 1; i >= 0; i--){
        while (!stk.empty() && arr[stk.top()] >= arr[i]) {
            stk.pop();
        }
        if (!stk.empty()) ans[i] = stk.top();
        stk.push(i);
    }
    return ans;
}

Putting it all together:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int solve(vector<int>& arr) {
    int n = arr.size(), max_area = 0, lo, hi, width, height;
    vector<int> left = NSL(arr);
    vector<int> right = NSR(arr);

    for (int i = 0; i < n; i++) {
        height = arr[i];
        lo = left[i], hi = right[i];
        width = hi - lo - 1;
        max_area = max(max_area, width * height);
    }
    return max_area;
}

Notice how we got rid of the two inner while loops in the naive approach!

Time Complexity of this approach is O(n)O(n).

Space Complexity is O(2n)O(2n) as we are using two arrays, left and right for storing NSL and NSR.

Can we do better ???

  • It is possible to solve this problem in a single pass using monostack, very similar to the way we solve the Next Greater to the Right (NGR) problem.

  • We push elements (bar heights) into the monostack in a strictly increasing order as we move form left to right. This is an invariant that we always maintain. Since, we care about the location of the elements, we push their indices instead of the values. We can always access the values as per our needs when we have the indices.

  • In the following section, I’ll be referring to the indices of bar heights as bar heights themselves.

Key Idea
While moving from left to right, we only keep the indices of the bar heights in the stack which have a potential to be further expanded towards the right.
  • If the current bar height bib_i is greater than the bar height on the top of the stack (or if the stack is empty ), then we simply push the index ii on the top of the stack and move on.

  • In our example, arr = [2, 7, 8, 4, 6] the array is strictly increasing till index 2. So, we simply add the indices into the stack sequentially.

/posts/largest_rectangle_in_histogram/stack_init.jpg
Figure showing stack after processing indices 0,1,2.
  • But when we encounter a bar height bib_i which is shorter than the bar height on the top of the stack, say bjb_j ( bj<bib_j < b_i and j<ij < i ), we can conclude that bjb_j cannot be expanded beyond index ii towards the right.

  • In our example, when i=3i = 3, bi=4b_i = 4. The bar height of the index on top of the stack j=2j = 2 is bj=8b_j = 8. So here, bj>bib_j > b_i as 8>48 > 4. We now come to know that the bar height bjb_j = 8 cannot be expanded further as bi=4b_i = 4 is not big enough to expand bjb_j’s rectangle.

/posts/largest_rectangle_in_histogram/at_index_4.jpg
Figure showing state at index 3. Note k<j<ik < j < i.
  • Since bjb_j was present in the stack so far, we know for sure that bjb_j can be expanded uptil index i1i-1. It remains to find out how much it it can be expanded to the left.

  • In our example, for bj=8b_j = 8, we know that bjb_j can be expanded only uptil index i1i - 1 i.e 31=23-1 = 2. This is our rightmost expansion point for bj=8b_j = 8.

  • To find the left expansion point, we can make use of of the fact that the stack is strictly increasing! Our left expansion point is simply the index of the bar bkb_k in the stack, below the top element bjb_j. This is because it is guaranteed that bkb_k < bjb_j (also k<jk < j) and hence, bjb_j can only be expanded uptil index k+1k+1 to the left. If bkb_k does not exist, then the stack will be empty. However, we can assume kk as 1-1 in this case for mathematical convenience.

  • In our example, for bj=8b_j = 8 the index kk is k=1k = 1 as bk=7b_k = 7 and bk<bjb_k < b_j. So the left expansion point for the bar height 88 is k+1=2k + 1 = 2.

/posts/largest_rectangle_in_histogram/left_and_right.png
Figure depicting left and right expansion points for bj=8b_j = 8.
  • At its core, the solution is simply a more elegant version of the second approach we saw earlier. bkb_k is the next smaller element to the left of bjb_j and bib_i is the next smaller element to the right of bjb_j.

  • So bar height bjb_j spans from k+1,k+2,j,,i1k+1,k+2,…j,…,i-1. The width of the rectangle it forms is ik1i - k - 1. ( Note that k<j<ik < j < i ). So the height of the rectangle is bjb_j and its width is ik1i - k - 1. Using them, we update our global maximum answer. After all this, we can say that we have completely processed element bjb_j. We pop index jj out of the stack.

  • We keep on popping out bar heights from the top of the stack until bib_i is smaller or equal to the bar height on the top of the stack. Once, we have processed all the bar heights from the stack we push index ii onto the stack with the hope of bib_i getting expanded further to the right.

  • If the stack is non-empty at the end, we process the remaining elements in the stack with the same algorithm, assuming we have a zero height bar at index nn as mentioned earlier ( We assume i=ni = n).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int solve(vector<int>& nums) {
    int n = nums.size();
    stack<int> stk;
    int max_area = 0 , cur_area , height , k , width;

    for(int i = 0; i < n ; i++){
        while(!stk.empty() && nums[stk.top()] >= nums[i]){
            height = nums[stk.top()];  // This height is bj
            stk.pop();
            k = stk.empty() ? -1 : stk.top();
            width = i - k - 1;
            cur_area = height * width;
            max_area = max(cur_area , max_area);
        }

        stk.push(i); // Pushing index i onto the stack after processing elements from stack.
    }

    // We process the remaining elements in the stack.
    while(!stk.empty()){
        height = nums[stk.top()];   // This height is bj
        stk.pop();
        k = stk.empty() ? -1 : stk.top();
        width = n - k - 1;          // In this case, i = n
        cur_area = height * width;
        max_area = max(cur_area , max_area);
    }

    return max_area;
}