In this post we will solve LeetCode 84. Largest Rectangle in Histogram problem using the Java programming language and the VSCode IDE on a Windows computer.
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. Constraints: o 1 <= heights.length <= 10^5 o 0 <= heights[i] <= 10^4 Related Topics: * Array o Stack * Monotonic Stack
We are given an array representing a histogram. The width of each bar holding a value is 1 unit. We are asked to return the area of the largest rectangle in the histogram.
We will implement two solutions for the function of interest. In the first we will use a window and arrays. In the second approach we will use a monotonic stack .
Since I will be solving the problem on my computer, I will require a test scaffold to read the input line, generate and populate the input array to the function of interest, call the function of interest and display the result. Unless you wish to keep the test code and the solutions in a single project, it is a lot simpler to use the online IDE provided by LeetCode.
It seems that in the Largest Rectangle – Part 1 and Largest Rectangle – Part 2 posts in this blog, we covered a slightly different set of requirements for a very similar problem.
public int largestRectangleArea(int[] heights) {
}
The signature for the function of interest requires as a single argument the `heights` int[] array. The function returns the largest rectangle in the histogram.
2,1,5,6,2,3 <<< heights[4]: 2 >= heights[6]: out of bounds <<< heights[3]: 6 >= heights[4]: 2 <<< heights[2]: 5 >= heights[4]: 2 <<< heights[1]: 1 >= heights[6]: out of bounds <<< heights[0]: 2 >= heights[1]: 1 <<< heights[-1]: out of bounds <= heights[1]: 1 <<< heights[1]: 1 <= heights[2]: 5 <<< heights[2]: 5 <= heights[3]: 6 <<< heights[1]: 1 <= heights[4]: 2 <<< heights[4]: 2 <= heights[5]: 3 <<< right: [1, 6, 4, 4, 6, 6] <<< left: [-1, -1, 1, 2, 1, 4] <<< width: 1 height[0]: 2 <<< area: 2 <<< maxArea: 2 <<< width: 6 height[1]: 1 <<< area: 6 <<< maxArea: 6 <<< width: 2 height[2]: 5 <<< area: 10 <<< maxArea: 10 <<< width: 1 height[3]: 6 <<< area: 6 <<< maxArea: 10 <<< width: 4 height[4]: 2 <<< area: 8 <<< maxArea: 10 <<< width: 1 height[5]: 3 <<< area: 3 <<< maxArea: 10 main <<< largestRectangleArea: 10 main <<< heights: [2, 1, 5, 6, 2, 3] <<< i: 0 height: 2 <<< ms: [0] <<< i: 1 height: 1 <<< j: 0 <<< width: 1 <<< area: 2 <<< maxArea: 2 <<< ms: [1] <<< i: 2 height: 5 <<< ms: [1, 2] <<< i: 3 height: 6 <<< ms: [1, 2, 3] <<< i: 4 height: 2 <<< j: 3 <<< width: 1 <<< area: 6 <<< maxArea: 6 <<< j: 2 <<< width: 2 <<< area: 10 <<< maxArea: 10 <<< ms: [1, 4] <<< i: 5 height: 3 <<< ms: [1, 4, 5] <<< i: 6 height: 0 <<< j: 5 <<< width: 1 <<< area: 3 <<< maxArea: 10 <<< j: 4 <<< width: 4 <<< area: 8 <<< maxArea: 10 <<< j: 1 <<< width: 6 <<< area: 6 <<< maxArea: 10 <<< ms: [6] main <<< largestRectangleArea0: 10 2,4 main <<< heights: [2, 4] <<< heights[0]: 2 >= heights[2]: out of bounds <<< heights[0]: 2 <= heights[1]: 4 <<< right: [2, 2] <<< left: [-1, 0] <<< width: 2 height[0]: 2 <<< area: 4 <<< maxArea: 4 <<< width: 1 height[1]: 4 <<< area: 4 <<< maxArea: 4 main <<< largestRectangleArea: 4 <<< i: 0 height: 2 <<< ms: [0] <<< i: 1 height: 4 <<< ms: [0, 1] <<< i: 2 height: 0 <<< j: 1 <<< width: 1 <<< area: 4 <<< maxArea: 4 <<< j: 0 <<< width: 2 <<< area: 4 <<< maxArea: 4 <<< ms: [2] main <<< largestRectangleArea0: 4
Test cases are separate from each other by two blank lines.
The first line in each test case is the input line. Our test scaffold which IS NOT PART OF THE SOLUTION, seems to read the input line and allocate and populate an int[] named `heights`. The contents of the array are then displayed to make sure all is well before calling the two implementations of the function of interest.
After calling the function of interest the test scaffold returns the output which is displayed at the end of each test case.
The output generated by the functions of interest is provided to allow us to track the operation of the algorithm in use. Please note that such output IS NOT PART OF THE SOLUTION. I removed the additional output from the code before submitting it for evaluation at LeetCode.
/**
* Test scaffold.
* !!! NOT PART OF SOLUTION !!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] heights ****
int[] heights = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< heights: " + Arrays.toString(heights));
// **** call function of interest and display result ****
System.out.println("main <<< largestRectangleArea0: " + largestRectangleArea0(heights));
// **** call function of interest and display result ****
System.out.println("main <<< largestRectangleArea: " + largestRectangleArea(heights));
}
The test code seems to follow closely the description of the test cases. I do not have anything else to add at this point in time.
/**
* Given an array of integers heights representing the histogram's bar height
* where the width of each bar is 1,
* return the area of the largest rectangle in the histogram.
*
* Runtime: O(n) - Space: O(n)
*
* Runtime: 21 ms, faster than 80.11% of Java online submissions.
* Memory Usage: 81.6 MB, less than 33.70% of Java online submissions.
*
* 96 / 96 test cases passed.
* Status: Accepted
* Runtime: 21 ms
* Memory Usage: 81.6 MB
*/
static public int largestRectangleArea(int[] heights) {
// **** sanity check(s) ****
int n = heights.length;
if (n == 0) return 0;
// **** initialization ****
int maxArea = 0;
int[] left = new int[n];
int[] right = new int[n];
left[0] = -1;
right[n - 1] = n;
// **** populate right array (right to left) ****
for (int i = n - 2; i >= 0; i--) {
// **** next index ****
int next = i + 1;
// **** look for heights[i] >= heights - O(n) ****
while (next < n && heights[next] >= heights[i])
next = right[next];
// **** populate this right entry ****
right[i] = next;
// ???? ????
System.out.print("<<< heights[" + i + "]: " + heights[i] + " >= heights[" + next + "]: ");
if (next >= n)
System.out.println("out of bounds");
else System.out.println(heights[next]);
}
// **** populate left array (left to right) - O(n) ****
for (int i = 1; i < n; i++) {
// **** previous index ****
int prev = i - 1;
// **** look for height <= heights[i] - O(n) ****
while (prev >= 0 && heights[prev] >= heights[i])
prev = left[prev];
// **** populate this left entry ****
left[i] = prev;
// ???? ????
System.out.print("<<< heights[" + prev + "]: ");
if (prev < 0)
System.out.print("out of bounds");
else System.out.print(heights[prev]);
System.out.println(" <= heights[" + i + "]: " + heights[i]);
}
// ???? ????
System.out.println("<<< right: " + Arrays.toString(right));
System.out.println("<<< left: " + Arrays.toString(left));
// **** loop computing and updating maxArea - O(n) ****
for (int i = 0; i < n; i++) {
// **** width of rectangle ****
int width = right[i] - left[i] - 1;
// ???? ????
System.out.println("<<< width: " + width + " height[" + i + "]: " + heights[i]);
// **** compute area ****
int area = heights[i] * width;
// ???? ????
System.out.println("<<< area: " + area);
// **** update maxArea (if needed) ****
maxArea = Math.max(maxArea, area);
// ???? ????
System.out.println("<<< maxArea: " + maxArea);
}
// **** return maxArea ****
return maxArea;
}
This is the first implementation of the function of interest.
For each value in the `heights` int[] array we need to determine a left and right set of boundaries at which the height of a rectangle is at least equal or higher than the current height.
The function starts by performing a sanity check.
The sanity check is followed by the initialization steps. We are declaring a `left` and a `right` int[] arrays to hold a window in which a candidate for the largest rectangle will be enclosed. The first entry in each array is set.
We then enter a loop in which we are populating the `right` int[] array. Note that we are interested in the indices for the right side of a window in which the height in the `heights` int[] array will be the right limit for the rectangle.
We then enter a similar loop in which we are populating the `left` int[] array. Note that we are interested in the indices for the left side of a window in which the height of in the `heights` int[] array will be the left limit for the rectangle of interest.
The contents of the `left` and `right` arrays are then displayed. Please take a few moments to understand the contents of the arrays. They contain indices to the values in the `heights` int[] array. They hold potencial ends for the largest rectangle in the histogram.
In the last loop we compute the area of the rectangles within the `left` and `right` arrays. The area of each rectangle is computed. We then store the largest area in the `maxArea`.
When all is said and done, the value of the `maxArea` is returned.
Please note in the comments section of the function the performance numbers for the implementation of the function of interest.
/**
* Given an array of integers heights representing the histogram's bar height
* where the width of each bar is 1,
* return the area of the largest rectangle in the histogram.
*
* Execution: O(n) - Space: O(n)
*
* Runtime: 79 ms, faster than 14.67% of Java online submissions.
* Memory Usage: 88.9 MB, less than 21.78% of Java online submissions.
*
* 96 / 96 test cases passed.
* Status: Accepted
* Runtime: 79 ms
* Memory Usage: 88.9 MB
*/
static public int largestRectangleArea0(int[] heights) {
// **** sanity check(s) ****
int n = heights.length;
if (n == 0) return 0;
// **** initialization ****
int maxArea = 0;
Stack<Integer> ms = new Stack<>();
// **** traverse input array - O(n) ****
for (int i = 0; i <= n; i++) {
// **** set current height ****
int height = i == n ? 0 : heights[i];
// ???? ????
System.out.println("<<< i: " + i + " height: " + height);
// **** loop computing and updating maxArea - O(1) ****
while (!ms.empty() && height < heights[ms.peek()]) {
// **** index from stack ****
int j = ms.pop();
// ???? ????
System.out.println("<<< j: " + j);
// **** compute width of rectangle *****
int width = ms.isEmpty() ? i : i - ms.peek() - 1;
// ???? ????
System.out.println("<<< width: " + width);
// **** compute rectangle area ****
int area = heights[j] * width;
// ???? ????
System.out.println("<<< area: " + area);
// **** update maxArea as needed ****
maxArea = Math.max(maxArea, area);
// ???? ????
System.out.println("<<< maxArea: " + maxArea);
}
// **** push current index ****
ms.push(i);
// ???? ????
System.out.println("<<< ms: " + ms.toString());
}
// **** return maxArea ****
return maxArea;
}
The second implementation of the function of interest will use a monotonic stack. The function start with the same sanity checks as the previous implementation.
For the initialization step we replace the two int[] arrays with a stack.
In the main loop we traverse the values in the `heights` int[] array.
We then encounter a while loop which is not entered if the stack is empty.
If we enter the while loop, we first get the index of the first bar in the histogram from the stack and put the value in `j`.
The width of the rectangle is computed. Now that we have the width and height we can compute the `area` of the current rectangle.
The `maxArea` is updated with the maximum area we have so far encountered.
After the while loop, we push into the `ms` stack the index of the current histogram bar.
When all is said and done, the function returns the value of the `maxArea`.
The comments section of this function holds the performance values for this implementation. Note that they are not as good as the ones of the first implementation. It seems that the implementation of the stack is quite expensive.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named LargestRectangleInHistogram.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John