Largest Rectangle in Histogram solution and explanation
Google
TCS
8 more videos on this problem
LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - PythonNeetCode · 17:20 · 414K views
L12. Largest Rectangle in Histogram | Stack and Queue Playlisttake U forward · 31:42 · 302K views
Largest Rectangle in Histogram | Part - 1 | Leetcode 84take U forward · 30:00 · 256K views
Largest rectangle in Histogram | Leetcode #84Techdose · 27:43 · 117K views
Largest Rectangle in Histogram | Best Solution & CodeShradha Khapra · 32:56 · 85K views
Largest Rectangle in Histogram - Leetcode 84 - Stacks (Python)Greg Hogg · 11:00 · 20K views
Coding Interview Problem - Largest Rectangle In HistogramKnapsack · 13:58 · 18K views
Largest Rectangle in Histogram | Live Coding with Explanation | Leetcode - 84Algorithms Made Easy · 12:51 · 8K views
Coding Interview Problem: Largest Rectangle in a HistogramJackson Gabbard · 16:18 · 312K views
The problem
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.
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 1050 <= heights[i] <= 104
Approach overview
Problem Overview: You are given an array where each element represents the height of a histogram bar. The goal is to find the largest rectangular area that can be formed using consecutive bars. The rectangle must use the full width of the selected bars and the minimum height among them.
Approach 1: Divide and Conquer (Average O(n log n), Worst O(n²) time, O(log n) space)
This approach mirrors the strategy used in problems like maximum subarray. For a given range, find the index of the minimum height bar. That bar becomes the limiting height of a rectangle spanning the entire range. Compute three candidates: rectangle using the minimum bar across the full width, best rectangle in the left subarray, and best rectangle in the right subarray. Recursively evaluate both halves and return the maximum. The method is intuitive but can degrade to O(n²) if the array is already sorted because the minimum element repeatedly splits the array unevenly.
Approach 2: Monotonic Stack Method (O(n) time, O(n) space)
This method uses a stack to maintain indices of histogram bars in increasing height order. While iterating through the array, push indices as long as heights keep increasing. When a smaller height appears, repeatedly pop from the stack because the popped bar can no longer extend further right. Calculate the area using the popped height as the smallest bar and the distance between the current index and the new stack top as the width. This stack is called a monotonic stack because heights remain ordered. Each bar is pushed and popped at most once, giving linear time complexity.
Recommended for interviews: The monotonic stack approach is what most interviewers expect. It demonstrates understanding of boundary expansion problems and efficient stack usage. The divide and conquer idea helps build intuition, but the O(n) stack solution shows stronger algorithmic optimization skills.
Approach 1: Monotonic Stack Method
This approach utilizes a monotonic stack to efficiently track the heights of the histogram bars. By iterating through the array and maintaining a stack of indices, we can pop the stack whenever we find a shorter bar, calculate the area of the rectangle formed with the popped bar as the shortest.bar and update the maximum area if necessary. The stack helps to find the left and right boundaries for each bar to compute the area.
def largestRectangleArea(heights):
stack = []
max_area = 0
i = 0
while i < len(heights) or stack:
if i < len(heights) and (not stack or heights[i] >= heights[stack[-1]]):
stack.append(i)
i += 1
else:
h = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * width)
return max_area
# Example usage
heights = [2, 1, 5, 6, 2, 3]
print(largestRectangleArea(heights)) # Output: 10import java.util.Stack;
public class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int max_area = 0;
int i = 0;
while (i < heights.length) {
if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
stack.push(i++);
} else {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
max_area = Math.max(max_area, height * width);
}
}
while (!stack.isEmpty()) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
max_area = Math.max(max_area, height * width);
}
return max_area;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println(solution.largestRectangleArea(heights)); // Outputs 10
}
}#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
int largestRectangleArea(std::vector<int>& heights) {
std::stack<int> stk;
int max_area = 0;
int i = 0;
while (i < heights.size() || !stk.empty()) {
if (stk.empty() || (i < heights.size() && heights[i] >= heights[stk.top()])) {
stk.push(i++);
} else {
int h = heights[stk.top()];
stk.pop();
int width = stk.empty() ? i : i - stk.top() - 1;
max_area = std::max(max_area, h * width);
}
}
return max_area;
}
int main() {
std::vector<int> heights = {2,1,5,6,2,3};
std::cout << largestRectangleArea(heights) << std::endl;
return 0;
}var largestRectangleArea = function(heights) {
let stack = [];
let maxArea = 0;
let i = 0;
while (i < heights.length || stack.length) {
if (i < heights.length && (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]])) {
stack.push(i++);
} else {
let height = heights[stack.pop()];
let width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
}
return maxArea;
};
// Example usage
console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])); // Output: 10#include <stdio.h>
#include <stdlib.h>
int largestRectangleArea(int* heights, int heightsSize) {
int* stack = (int*)malloc(sizeof(int) * (heightsSize + 1));
int top = -1;
int max_area = 0;
int i;
for (i = 0; i <= heightsSize; i++) {
while (top != -1 && (i == heightsSize || heights[i] < heights[stack[top]])) {
int height = heights[stack[top--]];
int width = (top == -1) ? i : i - stack[top] - 1;
int area = height * width;
if (area > max_area) {
max_area = area;
}
}
stack[++top] = i;
}
free(stack);
return max_area;
}
int main() {
int heights[] = {2,1,5,6,2,3};
int size = sizeof(heights) / sizeof(heights[0]);
printf("%d\n", largestRectangleArea(heights, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int LargestRectangleArea(int[] heights) {
Stack<int> stack = new Stack<int>();
int max_area = 0;
int i = 0;
while (i < heights.Length) {
if (stack.Count == 0 || heights[i] >= heights[stack.Peek()]) {
stack.Push(i++);
} else {
int height = heights[stack.Pop()];
int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
max_area = Math.Max(max_area, height * width);
}
}
while (stack.Count > 0) {
int height = heights[stack.Pop()];
int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
max_area = Math.Max(max_area, height * width);
}
return max_area;
}
public static void Main(String[] args) {
Solution sol = new Solution();
int[] heights = {2, 1, 5, 6, 2, 3};
Console.WriteLine(sol.LargestRectangleArea(heights)); // Outputs 10
}
}The Python solution also relies on the stack data structure for managing histogram bar indices. As each bar is processed, any found to be lower than the current stack's top leads to computing rectangle area, leveraging the current index and top's position for width determination. Max area updates follow each calculation, ensuring processing of all heights by monitoring the stack's contents to the end.
Time Complexity: O(n), each height contributes at most once to the stack processing.
Space Complexity: O(n) for the stack used in tracking.
Approach 2: Divide and Conquer
This approach is inspired by the algorithm for finding the maximum subarray sum, with the core idea to exploit the properties of minimal elements acting as the constraints. Here, smaller segments of the array are divided to compute maximum rectangular areas separately and then to combine comprehensive results. It works optimally when the heights array is transformed to assist binary division, allowing recursive calls to determine the peak areas between and within divisions.
def largestRectangleArea(heights):
def calculateArea(heights, start, end):
if start > end:
return 0
min_index = start
for i in range(start, end + 1):
if heights[i] < heights[min_index]:
min_index = i
left_area = calculateArea(heights, start, min_index - 1)
right_area = calculateArea(heights, min_index + 1, end)
current_area = heights[min_index] * (end - start + 1)
return max(current_area, left_area, right_area)
return calculateArea(heights, 0, len(heights) - 1)
# Example usage
heights = [2, 1, 5, 6, 2, 3]
print(largestRectangleArea(heights)) # Output: 10import java.util.Arrays;
public class Solution {
public int largestRectangleArea(int[] heights) {
return calculateArea(heights, 0, heights.length - 1);
}
private int calculateArea(int[] heights, int start, int end) {
if (start > end) return 0;
int min_index = start;
for (int i = start; i <= end; i++) {
if (heights[i] < heights[min_index])
min_index = i;
}
int left_area = calculateArea(heights, start, min_index - 1);
int right_area = calculateArea(heights, min_index + 1, end);
int current_area = heights[min_index] * (end - start + 1);
return Math.max(current_area, Math.max(left_area, right_area));
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println(sol.largestRectangleArea(heights)); // Outputs 10
}
}#include <iostream>
#include <vector>
#include <algorithm>
int calculateArea(const std::vector<int>& heights, int start, int end) {
if (start > end) return 0;
int min_index = start;
for (int i = start; i <= end; ++i) {
if (heights[i] < heights[min_index])
min_index = i;
}
int left_area = calculateArea(heights, start, min_index - 1);
int right_area = calculateArea(heights, min_index + 1, end);
int current_area = heights[min_index] * (end - start + 1);
return std::max({current_area, left_area, right_area});
}
int largestRectangleArea(std::vector<int>& heights) {
return calculateArea(heights, 0, heights.size() - 1);
}
int main() {
std::vector<int> heights = {2, 1, 5, 6, 2, 3};
std::cout << largestRectangleArea(heights) << std::endl;
return 0;
}var largestRectangleArea = function(heights) {
function calculateArea(heights, start, end) {
if (start > end) return 0;
let minIndex = start;
for (let i = start; i <= end; i++) {
if (heights[i] < heights[minIndex])
minIndex = i;
}
const currentArea = heights[minIndex] * (end - start + 1);
const leftArea = calculateArea(heights, start, minIndex - 1);
const rightArea = calculateArea(heights, minIndex + 1, end);
return Math.max(currentArea, Math.max(leftArea, rightArea));
}
return calculateArea(heights, 0, heights.length - 1);
};
// Example usage
console.log(largestRectangleArea([2, 1, 5, 6, 2, 3])); // Output: 10#include <stdio.h>
#include <limits.h>
int max(int a, int b, int c) {
return (a > b ? (a > c ? a : c) : (b > c ? b : c));
}
int calculateArea(int heights[], int start, int end) {
if (start > end) return 0;
int min_index = start;
for (int i = start; i <= end; i++) {
if (heights[i] < heights[min_index])
min_index = i;
}
int left_area = calculateArea(heights, start, min_index - 1);
int right_area = calculateArea(heights, min_index + 1, end);
int current_area = heights[min_index] * (end - start + 1);
return max(current_area, left_area, right_area);
}
int largestRectangleArea(int* heights, int heightsSize) {
return calculateArea(heights, 0, heightsSize - 1);
}
int main() {
int heights[] = {2,1,5,6,2,3};
int size = sizeof(heights) / sizeof(heights[0]);
printf("%d\n", largestRectangleArea(heights, size));
return 0;
}using System;
public class Solution {
public int LargestRectangleArea(int[] heights) {
return CalculateArea(heights, 0, heights.Length - 1);
}
private int CalculateArea(int[] heights, int start, int end) {
if (start > end) return 0;
int min_index = start;
for (int i = start; i <= end; i++) {
if (heights[i] < heights[min_index])
min_index = i;
}
int left_area = CalculateArea(heights, start, min_index - 1);
int right_area = CalculateArea(heights, min_index + 1, end);
int current_area = heights[min_index] * (end - start + 1);
return Math.Max(current_area, Math.Max(left_area, right_area));
}
public static void Main(String[] args) {
Solution sol = new Solution();
int[] heights = {2, 1, 5, 6, 2, 3};
Console.WriteLine(sol.LargestRectangleArea(heights)); // Outputs 10
}
}The Python function follows the divide and conquer rules established, determining minimum height within selected segments and solving for maximum rectangles via recursive advances into left and right segments. Using Python's max function ensures uniform maximum selection post evaluation.
Time Complexity: O(n^2), due to nested segment investigation.
Space Complexity: O(n), due to recursion stack usage.
Approach 3: Monotonic Stack
We can enumerate the height h of each bar as the height of the rectangle. Using a monotonic stack, we find the index left_i, right_i of the first bar with a height less than h to the left and right. The area of the rectangle at this time is h times (right_i-left_i-1). We can find the maximum value.
The time complexity is O(n), and the space complexity is O(n). Here, n represents the length of heights.
Common model of monotonic stack: Find the nearest number to the left/right of each number that is larger/smaller than it. Template:
stk = []
for i in range(n):
while stk and check(stk[-1], i):
stk.pop()
stk.append(i)
func largestRectangleArea(heights []int) int {
res, n := 0, len(heights)
var stk []int
left, right := make([]int, n), make([]int, n)
for i := range right {
right[i] = n
}
for i, h := range heights {
for len(stk) > 0 && heights[stk[len(stk)-1]] >= h {
right[stk[len(stk)-1]] = i
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
left[i] = stk[len(stk)-1]
} else {
left[i] = -1
}
stk = append(stk, i)
}
for i, h := range heights {
res = max(res, h*(right[i]-left[i]-1))
}
return res
}impl Solution {
#[allow(dead_code)]
pub fn largest_rectangle_area(heights: Vec<i32>) -> i32 {
let n = heights.len();
let mut left = vec![-1; n];
let mut right = vec![-1; n];
let mut stack: Vec<(usize, i32)> = Vec::new();
let mut ret = -1;
// Build left vector
for (i, h) in heights.iter().enumerate() {
while !stack.is_empty() && stack.last().unwrap().1 >= *h {
stack.pop();
}
if stack.is_empty() {
left[i] = -1;
} else {
left[i] = stack.last().unwrap().0 as i32;
}
stack.push((i, *h));
}
stack.clear();
// Build right vector
for (i, h) in heights.iter().enumerate().rev() {
while !stack.is_empty() && stack.last().unwrap().1 >= *h {
stack.pop();
}
if stack.is_empty() {
right[i] = n as i32;
} else {
right[i] = stack.last().unwrap().0 as i32;
}
stack.push((i, *h));
}
// Calculate the max area
for (i, h) in heights.iter().enumerate() {
ret = std::cmp::max(ret, (right[i] - left[i] - 1) * *h);
}
ret
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Monotonic Stack Method | Time Complexity: O(n), each height contributes at most once to the stack processing. |
| Divide and Conquer | Time Complexity: O(n^2), due to nested segment investigation. |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer | Average O(n log n), Worst O(n²) | O(log n) | Useful for conceptual understanding or when practicing recursive partitioning techniques |
| Monotonic Stack | O(n) | O(n) | Best general solution and the approach typically expected in coding interviews |
Frequently asked questions
Is Largest Rectangle in Histogram easy or hard?
Largest Rectangle in Histogram is classified as a Hard problem on LeetCode because the optimal solution requires recognizing a monotonic stack pattern. Many developers first attempt O(n^2) brute force approaches before discovering the linear stack-based optimization.
How to solve Largest Rectangle in Histogram in O(n)?
Use a monotonic increasing stack that stores indices of bars. Iterate through the histogram and maintain increasing heights. When a smaller height appears, pop bars from the stack and compute areas using the popped height as the limiting factor and the current index as the right boundary. Each index is processed once, giving linear time complexity.
Largest Rectangle in Histogram Python or Java solution
Both Python and Java implementations follow the same monotonic stack idea. Iterate through the histogram, push indices of increasing heights, and when a smaller bar appears, pop from the stack and compute areas using width derived from the current index and the new stack top. This guarantees O(n) runtime.
What is the best approach for Largest Rectangle in Histogram?
The monotonic stack approach is the most efficient and commonly used solution. It processes each bar once while maintaining indices of increasing heights in a stack. Whenever a smaller bar appears, rectangles are calculated using popped bars as the minimum height. This achieves O(n) time complexity with O(n) space.
What data structure is used in Largest Rectangle in Histogram?
The optimal solution relies on a stack, specifically a monotonic stack that maintains bars in increasing height order. The stack helps quickly determine the nearest smaller element on both sides of each bar, which defines the maximum width where that bar can form a rectangle.
What is the time complexity of Largest Rectangle in Histogram?
The optimal solution using a monotonic stack runs in O(n) time because each bar is pushed and popped from the stack at most once. A divide and conquer solution typically runs in O(n log n) on average but can degrade to O(n^2) in the worst case when the minimum element repeatedly splits the array unevenly.
Is Largest Rectangle in Histogram asked at Google, Amazon, or Meta?
Largest Rectangle in Histogram is a well-known hard interview problem frequently asked at large tech companies including Amazon, Google, Meta, and Microsoft. It tests understanding of stacks, boundary expansion problems, and algorithmic optimization from quadratic to linear time.