Problem of the day for today is Largest rectangle in a histogram: *Given n non-negative integers representing the histogram’s bar heights where the width of each bar is 1, find the area of largest rectangle in the histogram.*

In this example, we are given 7 heights [6, 2, 5, 4, 5, 1, 6] and can see that the area of the largest rectangle is 3*4 = 12.

If you want to try out this problem before looking at the solution, you can do that at the link provided above. I’ll try to explain my thought process for coming up with a solution.

The first insight is to determine which rectangles even need to be considered for the solution: those which cover a contiguous range of the input histogram (their width is integer – no point in covering half a bar) and whose height equals the minimum bar height in the range (rectangle height cannot exceed the minimum bar height in the range and there’s no point in considering a height less than the minimum height because we can just increase the height to the minimum height in the range and get a better solution). This greatly constrains the set of rectangles we need to consider. Formally, we need to consider only those rectangles with width = j-i+1 (0≤i≤j<n) and height = min(height[i..j]).

At this point, we can directly implement this solution. There are only n^2 choices for i and j. If we naively calculate the minimum height in the range [i..j], this will have time complexity O(n^3). Instead, we can keep track of the minimum height in the inner loop for j, leading to the following implementation with O(n^2) time complexity and O(1) auxiliary space complexity:

int largestRectangleArea(vector<int> &A) { | |

int maxArea = 0; | |

for (int i = 0; i < A.size(); i++) { | |

for (int j = i, mn = A[i]; j < A.size(); j++) { | |

mn = min(mn, A[j]); | |

maxArea = max(maxArea, (j-i+1) * mn); | |

} | |

} | |

return maxArea; | |

} |

We are still doing a lot of repeated work by considering all n^2 rectangles. There are only n possible heights. For each position j, we need to consider only 1 rectangle: the one with height = height[j] and width = k-i+1, where 0≤i≤j≤k<n, height[i..k] ≥ height[j], height[i-1] < height[j] and height[k+1] < height[j]. In the above example, for index 3, we need only consider the rectangle with height = 4 and width = 3 ([5, 4, 5]).

Put simply, we need to grow the rectangle from j towards left and right while the bar heights are greater than or equal to height[j]. If we do this naively, we’ll still end up with O(n^2) time complexity. If for any index j, we could find, in better than linear complexity, the first indices i (while going left from j) and k (while going right from j) where the bar height becomes smaller than height[j], we could solve this problem in complexity better than O(n^2).

There’s a trick to do this with a stack. We can precompute the left end of the rectangle situated at position i and having height = height[i] as follows:

vector posLeft(n); stack S; for (int i = 0; i < n; i++) { while (!S.empty() && height[S.top()] ≥ height[i]) S.pop(); posLeft[i] = S.empty() ? 0 : S.top() + 1; S.push(i); }

Each index is pushed onto the stack and popped off the stack only once, so the overall time complexity of this procedure is O(n). To get an intuition for what it is doing, observe that each bar gets rid of the higher bars on the left of it so that no bar on the right of it need to consider those indices.

Similarly, we can precompute the right end of the rectangle for each position i. This gives us the following implementation with O(n) space and time complexity:

int largestRectangleArea(vector<int> &A) { | |

int n = A.size(); | |

vector<int> posLeft(n); | |

stack<int> S; | |

for (int i = 0; i < n; i++) { | |

while (!S.empty() && A[S.top()] >= A[i]) | |

S.pop(); | |

posLeft[i] = S.empty() ? 0 : S.top() + 1; | |

S.push(i); | |

} | |

vector<int> posRight(n); | |

while (!S.empty()) S.pop(); | |

for (int i = n-1; i >= 0; i--) { | |

while (!S.empty() && A[S.top()] >= A[i]) | |

S.pop(); | |

posRight[i] = S.empty() ? n-1 : S.top() - 1; | |

S.push(i); | |

} | |

int maxArea = 0; | |

for (int i = 0; i < n; i++) | |

maxArea = max(maxArea, (posRight[i] - posLeft[i] + 1) * A[i]); | |

return maxArea; | |

} |

This should be a perfectly acceptable solution but we can do further optimizations. Observe that we don’t need to precompute and store both left and right ends. If we precompute the right ends, we can iterate from the left and compute the areas while computing the left ends (or we can do it the other way around).

int largestRectangleArea(vector<int> &A) { | |

int n = A.size(); | |

vector<int> posRight(n); | |

stack<int> S; | |

for (int i = n-1; i >= 0; i--) { | |

while (!S.empty() && A[S.top()] >= A[i]) | |

S.pop(); | |

posRight[i] = S.empty() ? n-1 : S.top() - 1; | |

S.push(i); | |

} | |

while (!S.empty()) S.pop(); | |

int maxArea = 0; | |

for (int i = 0; i < n; i++) { | |

while (!S.empty() && A[S.top()] >= A[i]) | |

S.pop(); | |

long long area = A[i] * (posRight[i] + 1 - (S.empty() ? 0 : S.top() + 1)); | |

if (area > maxArea) | |

maxArea = area; | |

S.push(i); | |

} | |

return maxArea; | |

} |

Oh but there’s still more optimizations that we can do. Observe when an index gets popped off the stack. This happens because we find the first index (on the right of it) which has a smaller height. This already gives us the right end of the rectangle. So we don’t need to precompute either the left or the right ends of the rectangle. Unfortunately, the space and time complexity is still O(n) but the solution is much prettier!

int largestRectangleArea(vector<int> &A) { | |

A.push_back(0); // sentinel to ensure all indices get popped off the stack | |

stack<int> S; | |

int maxArea = 0; | |

for (int i = 0; i < A.size(); i++) { | |

while (!S.empty() && A[S.top()] >= A[i]) { | |

int height = A[S.top()]; | |

S.pop(); | |

int left = S.empty() ? 0 : S.top() + 1, right = i - 1; | |

maxArea = max(maxArea, (right - left + 1) * height); | |

} | |

S.push(i); | |

} | |

return maxArea; | |

} |

Pingback: Problem of the day: Queue with min operation | Everything Under The Sun