.png)
Largest Rectangle in Histogram
Problem Statement
You are given an array heights[] where each element represents the height of a bar in a histogram.
Each bar has a width of 1.
Find the area of the largest rectangle that can be formed within the histogram.
Example 1
Input
heights = [2,1,5,6,2,3]
Output
10
Explanation
The largest rectangle is formed by bars of height 5 and 6 with width 2.
Area = 5 × 2 = 10
Example 2
Input
heights = [2,4]
Output
4
Why This Problem Is Important
- Classic stack-based interview question
- Tests monotonic stack understanding
- Used in matrix rectangle problems
- Appears frequently in FAANG interviews
- Foundation for advanced histogram problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Better Brute (Expand Left & Right) | O(n²) | O(1) |
| Approach 3 | Stack (Optimal) | O(n) | O(n) |
Approach 1: Brute Force
Idea
For every bar, try extending to the right and calculate the minimum height.
Algorithm
- For each index i
- Set minHeight = heights[i]
- For every index j ≥ i
- minHeight = min(minHeight, heights[j])
- Area = minHeight × (j - i + 1)
- Track maximum area
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
C
#include
int main() {
int h[] = {2,1,5,6,2,3};
int n = 6, maxArea = 0;
for(int i = 0; i < n; i++) {
int minH = h[i];
for(int j = i; j < n; j++) {
if(h[j] < minH) minH = h[j];
int area = minH * (j - i + 1);
if(area > maxArea) maxArea = area;
}
}
printf("Input: [2,1,5,6,2,3]\n");
printf("Output: %d\n", maxArea);
return 0;
}
C++
#include
using namespace std;
int main() {
int h[] = {2,1,5,6,2,3};
int n = 6, maxArea = 0;
for(int i = 0; i < n; i++) {
int minH = h[i];
for(int j = i; j < n; j++) {
minH = min(minH, h[j]);
maxArea = max(maxArea, minH * (j - i + 1));
}
}
cout << "Input: [2,1,5,6,2,3]" << endl;
cout << "Output: " << maxArea << endl;
return 0;
}
Java
public class HistogramBrute {
public static void main(String[] args) {
int[] h = {2,1,5,6,2,3};
int maxArea = 0;
for(int i = 0; i < h.length; i++) {
int minH = h[i];
for(int j = i; j < h.length; j++) {
minH = Math.min(minH, h[j]);
maxArea = Math.max(maxArea, minH * (j - i + 1));
}
}
System.out.println("Input: [2,1,5,6,2,3]");
System.out.println("Output: " + maxArea);
}
}
Python
h = [2,1,5,6,2,3]
n = len(h)
maxArea = 0
for i in range(n):
minH = h[i]
for j in range(i, n):
minH = min(minH, h[j])
maxArea = max(maxArea, minH * (j - i + 1))
print("Input: [2,1,5,6,2,3]")
print("Output:", maxArea)
JavaScript
let h = [2,1,5,6,2,3];
let maxArea = 0;
for (let i = 0; i < h.length; i++) {
let minH = h[i];
for (let j = i; j < h.length; j++) {
minH = Math.min(minH, h[j]);
maxArea = Math.max(maxArea, minH * (j - i + 1));
}
}
console.log("Input: [2,1,5,6,2,3]");
console.log("Output:", maxArea);
C#
using System;
class Program {
static void Main() {
int[] h = {2,1,5,6,2,3};
int maxArea = 0;
for(int i = 0; i < h.Length; i++) {
int minH = h[i];
for(int j = i; j < h.Length; j++) {
minH = Math.Min(minH, h[j]);
maxArea = Math.Max(maxArea, minH * (j - i + 1));
}
}
Console.WriteLine("Input: [2,1,5,6,2,3]");
Console.WriteLine("Output: " + maxArea);
}
}
Final Output
Input: [2,1,5,6,2,3]
Output: 10
Approach 2: Better Brute (Expand Left & Right)
Idea
For each bar, expand left and right while height ≥ current bar.
Algorithm
- For each index i
- Move left while height ≥ h[i]
- Move right while height ≥ h[i]
- Width = right - left - 1
- Area = h[i] × width
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
C
#include
int main() {
int h[] = {2,1,5,6,2,3};
int n = 6, maxArea = 0;
for(int i = 0; i < n; i++) {
int left = i, right = i;
while(left > 0 && h[left - 1] >= h[i]) left--;
while(right < n - 1 && h[right + 1] >= h[i]) right++;
int width = right - left + 1;
int area = h[i] * width;
if(area > maxArea) maxArea = area;
}
printf("Input: [2,1,5,6,2,3]\n");
printf("Output: %d\n", maxArea);
return 0;
}
C++
#include
using namespace std;
int main() {
int h[] = {2,1,5,6,2,3};
int n = 6, maxArea = 0;
for(int i = 0; i < n; i++) {
int left = i, right = i;
while(left > 0 && h[left - 1] >= h[i]) left--;
while(right < n - 1 && h[right + 1] >= h[i]) right++;
int width = right - left + 1;
maxArea = max(maxArea, h[i] * width);
}
cout << "Input: [2,1,5,6,2,3]" << endl;
cout << "Output: " << maxArea << endl;
return 0;
}
Java
public class HistogramBetterBrute {
public static void main(String[] args) {
int[] h = {2,1,5,6,2,3};
int maxArea = 0;
for(int i = 0; i < h.length; i++) {
int left = i, right = i;
while(left > 0 && h[left - 1] >= h[i]) left--;
while(right < h.length - 1 && h[right + 1] >= h[i]) right++;
int width = right - left + 1;
maxArea = Math.max(maxArea, h[i] * width);
}
System.out.println("Input: [2,1,5,6,2,3]");
System.out.println("Output: " + maxArea);
}
}
Python
h = [2,1,5,6,2,3]
n = len(h)
maxArea = 0
for i in range(n):
left = i
right = i
while left > 0 and h[left - 1] >= h[i]:
left -= 1
while right < n - 1 and h[right + 1] >= h[i]:
right += 1
width = right - left + 1
maxArea = max(maxArea, h[i] * width)
print("Input: [2,1,5,6,2,3]")
print("Output:", maxArea)
JavaScript
let h = [2,1,5,6,2,3];
let maxArea = 0;
for (let i = 0; i < h.length; i++) {
let left = i, right = i;
while (left > 0 && h[left - 1] >= h[i]) left--;
while (right < h.length - 1 && h[right + 1] >= h[i]) right++;
let width = right - left + 1;
maxArea = Math.max(maxArea, h[i] * width);
}
console.log("Input: [2,1,5,6,2,3]");
console.log("Output:", maxArea);
C#
using System;
class Program {
static void Main() {
int[] h = {2,1,5,6,2,3};
int maxArea = 0;
for(int i = 0; i < h.Length; i++) {
int left = i, right = i;
while(left > 0 && h[left - 1] >= h[i]) left--;
while(right < h.Length - 1 && h[right + 1] >= h[i]) right++;
int width = right - left + 1;
maxArea = Math.Max(maxArea, h[i] * width);
}
Console.WriteLine("Input: [2,1,5,6,2,3]");
Console.WriteLine("Output: " + maxArea);
}
}
Final Output
Input: [2,1,5,6,2,3]
Output: 10
Approach 3: Stack (Optimal)
Idea
Use a monotonic increasing stack.
When a smaller bar appears, calculate area of popped bars.
Algorithm
- Use stack to store indices
- Traverse bars
- While stack not empty and current bar < stack top:
- Pop height
- Width = current index - stack top - 1
- Push index
- Process remaining stack
Time & Space Complexity
- Time: O(n)
- Space: O(n)
C
#include
int main() {
int h[] = {2,1,5,6,2,3};
int n = 6;
int stack[100], top = -1;
int maxArea = 0;
for(int i = 0; i <= n; i++) {
int currHeight = (i == n) ? 0 : h[i];
while(top != -1 && h[stack[top]] > currHeight) {
int height = h[stack[top--]];
int width = (top == -1) ? i : i - stack[top] - 1;
int area = height * width;
if(area > maxArea) maxArea = area;
}
stack[++top] = i;
}
printf("Input: [2,1,5,6,2,3]\n");
printf("Output: %d\n", maxArea);
return 0;
}
C++
#include
#include
using namespace std;
int main() {
int h[] = {2,1,5,6,2,3};
int n = 6;
stack st;
int maxArea = 0;
for(int i = 0; i <= n; i++) {
int currHeight = (i == n) ? 0 : h[i];
while(!st.empty() && h[st.top()] > currHeight) {
int height = h[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = max(maxArea, height * width);
}
st.push(i);
}
cout << "Input: [2,1,5,6,2,3]" << endl;
cout << "Output: " << maxArea << endl;
return 0;
}
Java
import java.util.Stack;
public class HistogramOptimal {
public static void main(String[] args) {
int[] h = {2,1,5,6,2,3};
Stack st = new Stack<>();
int maxArea = 0;
for(int i = 0; i <= h.length; i++) {
int currHeight = (i == h.length) ? 0 : h[i];
while(!st.isEmpty() && h[st.peek()] > currHeight) {
int height = h[st.pop()];
int width = st.isEmpty() ? i : i - st.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
st.push(i);
}
System.out.println("Input: [2,1,5,6,2,3]");
System.out.println("Output: " + maxArea);
}
}
Python
h = [2,1,5,6,2,3]
stack = []
maxArea = 0
n = len(h)
for i in range(n + 1):
currHeight = 0 if i == n else h[i]
while stack and h[stack[-1]] > currHeight:
height = h[stack.pop()]
width = i if not stack else i - stack[-1] - 1
maxArea = max(maxArea, height * width)
stack.append(i)
print("Input: [2,1,5,6,2,3]")
print("Output:", maxArea)
JavaScript
let h = [2,1,5,6,2,3];
let stack = [];
let maxArea = 0;
let n = h.length;
for (let i = 0; i <= n; i++) {
let currHeight = (i === n) ? 0 : h[i];
while (stack.length && h[stack[stack.length - 1]] > currHeight) {
let height = h[stack.pop()];
let width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
console.log("Input: [2,1,5,6,2,3]");
console.log("Output:", maxArea);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] h = {2,1,5,6,2,3};
Stack st = new Stack();
int maxArea = 0;
for(int i = 0; i <= h.Length; i++) {
int currHeight = (i == h.Length) ? 0 : h[i];
while(st.Count > 0 && h[st.Peek()] > currHeight) {
int height = h[st.Pop()];
int width = st.Count == 0 ? i : i - st.Peek() - 1;
maxArea = Math.Max(maxArea, height * width);
}
st.Push(i);
}
Console.WriteLine("Input: [2,1,5,6,2,3]");
Console.WriteLine("Output: " + maxArea);
}
}
Final Output
Input: [2,1,5,6,2,3]
Output: 10
Summary
- Brute force is intuitive but slow
- Expand left-right improves clarity but still O(n²)
- Stack approach is optimal and interview-preferred
- Monotonic stack is the key concept
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
