Largest Rectangular Area in a Histogram
Program for Largest Rectangular Area in a Histogram
You are provided with an array of integers called heights, where each element heights[i] represents the height of a bar in a histogram. The width of each bar is fixed at 1 unit. The histogram consists of several vertical bars placed side by side, creating a continuous chart.
Your goal is to determine the maximum area of a rectangle that can be formed using one or more consecutive bars in the histogram. The rectangle’s area is calculated by multiplying the height of the shortest bar in the selected range by the total number of bars considered (width).
You need to return the largest possible rectangular area that can be formed from any combination of bars in the histogram.
Example 1
Input: heights = [7,1,7,2,2,4]
Output: 8
Output: 8
Example 2
Input: heights = [1,3,7]
Output: 7
Output: 7
Constraints:
- 1 <= heights.length <= 1000.
- 0 <= heights[i] <= 1000
Program for Largest Rectangular Area in Histogram Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A rectangle has a height and a width. Can you visualize how rectangles are formed in the given input? Considering one bar at a time might help. We can try to form rectangles by going through every bar and current bar’s height will be the height of the rectangle. How can you determine the width of the rectangle for the current bar being the height of the rectangle? Extending the current bar to the left and right might help determine the rectangle’s width.
Hint 2 :
For a bar with height h, try extending it to the left and right. We can see that we can’t extend further when we encounter a bar with a smaller height than h. The width will be the number of bars within this extended range. A brute force solution would be to go through every bar and find the area of the rectangle it can form by extending towards the left and right. This would be an O(n^2) solution. Can you think of a better way? Maybe precomputing the left and right boundaries might be helpful.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Divide and Conquer(Segment Tree) Method
- Stack Method
- Stack(Optimal) Method
- Stack(One Pass) Method
1. Brute Force Method
Check all possible rectangles by iterating through each bar and calculating the area, resulting in a time complexity of O(n^2).
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int largestRectangleArea(vector& heights) {
int n = heights.size();
int maxArea = 0;
for (int i = 0; i < n; i++) {
int height = heights[i];
int rightMost = i + 1;
while (rightMost < n && heights[rightMost] >= height) {
rightMost++;
}
int leftMost = i;
while (leftMost >= 0 && heights[leftMost] >= height) {
leftMost--;
}
rightMost--;
leftMost++;
maxArea = max(maxArea, height * (rightMost - leftMost + 1));
}
return maxArea;
}
};
Java
public class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int maxArea = 0;
for (int i = 0; i < n; i++) {
int height = heights[i];
int rightMost = i + 1;
while (rightMost < n && heights[rightMost] >= height) {
rightMost++;
}
int leftMost = i;
while (leftMost >= 0 && heights[leftMost] >= height) {
leftMost--;
}
rightMost--;
leftMost++;
maxArea = Math.max(maxArea, height * (rightMost - leftMost + 1));
}
return maxArea;
}
}
Python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
maxArea = 0
for i in range(n):
height = heights[i]
rightMost = i + 1
while rightMost < n and heights[rightMost] >= height:
rightMost += 1
leftMost = i
while leftMost >= 0 and heights[leftMost] >= height:
leftMost -= 1
rightMost -= 1
leftMost += 1
maxArea = max(maxArea, height * (rightMost - leftMost + 1))
return maxArea
JavaScript
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
largestRectangleArea(heights) {
const n = heights.length;
let maxArea = 0;
for (let i = 0; i < n; i++) {
let height = heights[i];
let rightMost = i + 1;
while (rightMost < n && heights[rightMost] >= height) {
rightMost++;
}
let leftMost = i;
while (leftMost >= 0 && heights[leftMost] >= height) {
leftMost--;
}
rightMost--;
leftMost++;
maxArea = Math.max(maxArea, height * (rightMost - leftMost + 1));
}
return maxArea;
}
}
2. Divide and Conquer(Segment Tree) Method
Recursively divide the histogram into smaller parts, find the minimum bar in each part, and calculate the maximum area. This method uses a segment tree for efficiency.
- Time complexity: O(n logn)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class MinIdx_Segtree {
public:
int n;
const int INF = 1e9;
vector A;
vector tree;
MinIdx_Segtree(int N, vector& a) {
this->n = N;
this->A = a;
while (__builtin_popcount(n) != 1) {
A.push_back(INF);
n++;
}
tree.resize(2 * n);
build();
}
void build() {
for (int i = 0; i < n; i++) {
tree[n + i] = i;
}
for (int j = n - 1; j >= 1; j--) {
int a = tree[j<<1];
int b = tree[(j<<1) + 1];
if(A[a]<=A[b])tree[j]=a;
else tree[j] = b;
}
}
void update(int i, int val) {
A[i] = val;
for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
int a = tree[j<<1];
int b = tree[(j<<1) + 1];
if(A[a]<=A[b])tree[j]=a;
else tree[j] = b;
}
}
int query(int ql, int qh) {
return query(1, 0, n - 1, ql, qh);
}
int query(int node, int l, int h, int ql, int qh) {
if (ql > h || qh < l) return INF;
if (l >= ql && h <= qh) return tree[node];
int a = query(node << 1, l, (l + h) >> 1, ql, qh);
int b = query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
if(a==INF)return b;
if(b==INF)return a;
return A[a]<=A[b]?a:b;
}
};
class Solution {
public:
int getMaxArea(vector& heights, int l, int r, MinIdx_Segtree& st) {
if (l > r) return 0;
if (l == r) return heights[l];
int minIdx = st.query(l, r);
return max(max(getMaxArea(heights, l, minIdx - 1, st),
getMaxArea(heights, minIdx + 1, r, st)),
(r - l + 1) * heights[minIdx]);
}
int largestRectangleArea(vector& heights) {
int n = heights.size();
MinIdx_Segtree st(n, heights);
return getMaxArea(heights, 0, n - 1, st);
}
};
Java
public class MinIdx_Segtree {
int n;
final int INF = (int) 1e9;
int[] A, tree;
public MinIdx_Segtree(int N, int[] heights) {
this.n = N;
this.A = heights;
while (Integer.bitCount(n) != 1) {
A = java.util.Arrays.copyOf(A, n + 1);
A[n] = INF;
n++;
}
tree = new int[2 * n];
build();
}
public void build() {
for (int i = 0; i < n; i++) {
tree[n + i] = i;
}
for (int j = n - 1; j >= 1; j--) {
int a = tree[j << 1];
int b = tree[(j << 1) + 1];
if (A[a] <= A[b]) {
tree[j] = a;
} else {
tree[j] = b;
}
}
}
public void update(int i, int val) {
A[i] = val;
for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
int a = tree[j << 1];
int b = tree[(j << 1) + 1];
if (A[a] <= A[b]) {
tree[j] = a;
} else {
tree[j] = b;
}
}
}
public int query(int ql, int qh) {
return query(1, 0, n - 1, ql, qh);
}
public int query(int node, int l, int h, int ql, int qh) {
if (ql > h || qh < l) return INF;
if (l >= ql && h <= qh) return tree[node];
int a = query(node << 1, l, (l + h) >> 1, ql, qh);
int b = query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
if (a == INF) return b;
if (b == INF) return a;
return A[a] <= A[b] ? a : b;
}
}
public class Solution {
public int getMaxArea(int[] heights, int l, int r, MinIdx_Segtree st) {
if (l > r) return 0;
if (l == r) return heights[l];
int minIdx = st.query(l, r);
return Math.max(Math.max(getMaxArea(heights, l, minIdx - 1, st),
getMaxArea(heights, minIdx + 1, r, st)),
(r - l + 1) * heights[minIdx]);
}
public int largestRectangleArea(int[] heights) {
int n = heights.length;
MinIdx_Segtree st = new MinIdx_Segtree(n, heights);
return getMaxArea(heights, 0, n - 1, st);
}
}
Python
class MinIdx_Segtree:
def __init__(self, N, A):
self.n = N
self.INF = int(1e9)
self.A = A
while (self.n & (self.n - 1)) != 0:
self.A.append(self.INF)
self.n += 1
self.tree = [0] * (2 * self.n)
self.build()
def build(self):
for i in range(self.n):
self.tree[self.n + i] = i
for j in range(self.n - 1, 0, -1):
a = self.tree[j << 1]
b = self.tree[(j << 1) + 1]
if self.A[a] <= self.A[b]:
self.tree[j] = a
else:
self.tree[j] = b
def update(self, i, val):
self.A[i] = val
j = (self.n + i) >> 1
while j >= 1:
a = self.tree[j << 1]
b = self.tree[(j << 1) + 1]
if self.A[a] <= self.A[b]:
self.tree[j] = a
else:
self.tree[j] = b
j >>= 1
def query(self, ql, qh):
return self._query(1, 0, self.n - 1, ql, qh)
def _query(self, node, l, h, ql, qh):
if ql > h or qh < l:
return self.INF
if l >= ql and h <= qh:
return self.tree[node]
a = self._query(node << 1, l, (l + h) >> 1, ql, qh)
b = self._query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh)
if a == self.INF:
return b
if b == self.INF:
return a
return a if self.A[a] <= self.A[b] else b
class Solution:
def getMaxArea(self, heights, l, r, st):
if l > r:
return 0
if l == r:
return heights[l]
minIdx = st.query(l, r)
return max(max(self.getMaxArea(heights, l, minIdx - 1, st),
self.getMaxArea(heights, minIdx + 1, r, st)),
(r - l + 1) * heights[minIdx])
def largestRectangleArea(self, heights):
n = len(heights)
st = MinIdx_Segtree(n, heights)
return self.getMaxArea(heights, 0, n - 1, st)
JavaScript
class MinIdx_Segtree {
/**
* @param {number} N
* @param {number[]} heights
*/
constructor(N, heights) {
this.n = N;
this.INF = 1e9;
this.A = heights.slice();
while ((this.n & (this.n - 1)) !== 0) {
this.A.push(this.INF);
this.n++;
}
this.tree = new Array(2 * this.n).fill(0);
this.build();
}
build() {
for (let i = 0; i < this.n; i++) {
this.tree[this.n + i] = i;
}
for (let j = this.n - 1; j >= 1; j--) {
let a = this.tree[j << 1];
let b = this.tree[(j << 1) + 1];
this.tree[j] = this.A[a] <= this.A[b] ? a : b;
}
}
/**
* @param {number} i
* @param {number} val
*/
update(i, val) {
this.A[i] = val;
for (let j = (this.n + i) >> 1; j >= 1; j >>= 1) {
let a = this.tree[j << 1];
let b = this.tree[(j << 1) + 1];
this.tree[j] = this.A[a] <= this.A[b] ? a : b;
}
}
/**
* @param {number} ql
* @param {number} qh
* @return {number}
*/
query(ql, qh) {
return this._query(1, 0, this.n - 1, ql, qh);
}
_query(node, l, h, ql, qh) {
if (ql > h || qh < l) return this.INF;
if (l >= ql && h <= qh) return this.tree[node];
let a = this._query(node << 1, l, (l + h) >> 1, ql, qh);
let b = this._query((node << 1) + 1, ((l + h) >> 1) + 1, h, ql, qh);
if (a === this.INF) return b;
if (b === this.INF) return a;
return this.A[a] <= this.A[b] ? a : b;
}
}
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
largestRectangleArea(heights) {
const n = heights.length;
const st = new MinIdx_Segtree(n, heights);
return this.getMaxArea(heights, 0, n - 1, st);
}
/**
* @param {number[]} heights
* @param {number} l
* @param {number} r
* @param {MinIdx_Segtree} st
* @return {number}
*/
getMaxArea(heights, l, r, st) {
if (l > r) return 0;
if (l === r) return heights[l];
const minIdx = st.query(l, r);
return Math.max(
this.getMaxArea(heights, l, minIdx - 1, st),
this.getMaxArea(heights, minIdx + 1, r, st),
(r - l + 1) * heights[minIdx]
);
}
}
3. Stack Method
Use a stack to keep track of bars and calculate areas when a smaller bar is encountered, maintaining a time complexity of O(n).
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int largestRectangleArea(vector& heights) {
int n = heights.size();
vector leftMost(n, -1);
vector rightMost(n, n);
stack stack;
for (int i = 0; i < n; i++) {
while (!stack.empty() && heights[stack.top()] >= heights[i]) {
stack.pop();
}
if (!stack.empty()) {
leftMost[i] = stack.top();
}
stack.push(i);
}
while (!stack.empty()) stack.pop();
for (int i = n - 1; i >= 0; i--) {
while (!stack.empty() && heights[stack.top()] >= heights[i]) {
stack.pop();
}
if (!stack.empty()) {
rightMost[i] = stack.top();
}
stack.push(i);
}
int maxArea = 0;
for (int i = 0; i < n; i++) {
leftMost[i] += 1;
rightMost[i] -= 1;
maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1));
}
return maxArea;
}
};
Java
public class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] leftMost = new int[n];
int[] rightMost = new int[n];
Stack stack = new Stack<>();
for (int i = 0; i < n; i++) {
leftMost[i] = -1;
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
leftMost[i] = stack.peek();
}
stack.push(i);
}
stack.clear();
for (int i = n - 1; i >= 0; i--) {
rightMost[i] = n;
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
if (!stack.isEmpty()) {
rightMost[i] = stack.peek();
}
stack.push(i);
}
int maxArea = 0;
for (int i = 0; i < n; i++) {
leftMost[i] += 1;
rightMost[i] -= 1;
maxArea = Math.max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1));
}
return maxArea;
}
}
Python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stack = []
leftMost = [-1] * n
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
leftMost[i] = stack[-1]
stack.append(i)
stack = []
rightMost = [n] * n
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
if stack:
rightMost[i] = stack[-1]
stack.append(i)
maxArea = 0
for i in range(n):
leftMost[i] += 1
rightMost[i] -= 1
maxArea = max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1))
return maxArea
JavaScript
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
largestRectangleArea(heights) {
const n = heights.length;
const leftMost = Array(n).fill(-1);
const rightMost = Array(n).fill(n);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
stack.pop();
}
if (stack.length) {
leftMost[i] = stack[stack.length - 1];
}
stack.push(i);
}
stack.length = 0;
for (let i = n - 1; i >= 0; i--) {
while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
stack.pop();
}
if (stack.length) {
rightMost[i] = stack[stack.length - 1];
}
stack.push(i);
}
let maxArea = 0;
for (let i = 0; i < n; i++) {
leftMost[i] += 1;
rightMost[i] -= 1;
maxArea = Math.max(maxArea, heights[i] * (rightMost[i] - leftMost[i] + 1));
}
return maxArea;
}
}
4. Stack(Optimal) Method
Optimize the stack approach by adding a sentinel bar at the end to simplify area calculations, ensuring all remaining bars are processed in one pass.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int largestRectangleArea(vector& heights) {
int maxArea = 0;
stack> stack; // pair: (index, height)
for (int i = 0; i < heights.size(); i++) {
int start = i;
while (!stack.empty() && stack.top().second > heights[i]) {
pair top = stack.top();
int index = top.first;
int height = top.second;
maxArea = max(maxArea, height * (i - index));
start = index;
stack.pop();
}
stack.push({ start, heights[i] });
}
while (!stack.empty()) {
int index = stack.top().first;
int height = stack.top().second;
maxArea = max(maxArea, height * (static_cast(heights.size()) - index));
stack.pop();
}
return maxArea;
}
};
Java
class Solution {
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
Stack stack = new Stack<>(); // pair: (index, height)
for (int i = 0; i < heights.length; i++) {
int start = i;
while (!stack.isEmpty() && stack.peek()[1] > heights[i]) {
int[] top = stack.pop();
int index = top[0];
int height = top[1];
maxArea = Math.max(maxArea, height * (i - index));
start = index;
}
stack.push(new int[]{start, heights[i]});
}
for (int[] pair : stack) {
int index = pair[0];
int height = pair[1];
maxArea = Math.max(maxArea, height * (heights.length - index));
}
return maxArea;
}
}
Python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
stack = [] # pair: (index, height)
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index
stack.append((start, h))
for i, h in stack:
maxArea = max(maxArea, h * (len(heights) - i))
return maxArea
JavaScript
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
largestRectangleArea(heights) {
let maxArea = 0;
const stack = []; // pair: (index, height)
for (let i = 0; i < heights.length; i++) {
let start = i;
while (
stack.length > 0 &&
stack[stack.length - 1][1] > heights[i]
) {
const [index, height] = stack.pop();
maxArea = Math.max(maxArea, height * (i - index));
start = index;
}
stack.push([start, heights[i]]);
}
for (const [index, height] of stack) {
maxArea = Math.max(maxArea, height * (heights.length - index));
}
return maxArea;
}
}
5. Stack(One Pass) Method
Traverse the entire histogram once while maintaining a stack to store indices, calculating the largest rectangle area in a single pass.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int largestRectangleArea(vector& heights) {
int n = heights.size();
int maxArea = 0;
stack stack;
for (int i = 0; i <= n; i++) {
while (!stack.empty() &&
(i == n || heights[stack.top()] >= heights[i])) {
int height = heights[stack.top()];
stack.pop();
int width = stack.empty() ? i : i - stack.top() - 1;
maxArea = max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
};
Java
public class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int maxArea = 0;
Stack stack = new Stack<>();
for (int i = 0; i <= n; i++) {
while (!stack.isEmpty() &&
(i == n || heights[stack.peek()] >= heights[i])) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
}
Python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
maxArea = 0
stack = []
for i in range(n + 1):
while stack and (i == n or heights[stack[-1]] >= heights[i]):
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
maxArea = max(maxArea, height * width)
stack.append(i)
return maxArea
JavaScript
class Solution {
/**
* @param {number[]} heights
* @return {number}
*/
largestRectangleArea(heights) {
const n = heights.length;
let maxArea = 0;
const stack = [];
for (let i = 0; i <= n; i++) {
while (stack.length &&
(i === n || heights[stack[stack.length - 1]] >= heights[i])) {
const height = heights[stack.pop()];
const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
}
