Largest Rectangle in Histogram Editorial

Practice Problem Link: Largest Rectangle In Histogram

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a list of non-negative integers denoting the bar heights of a histogram. All the bars have a width of 1. You need to find the area of the largest possible rectangle in the histogram.

Naive Approach

The simple solution is to find the maximum area among all the possible subarrays.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int getLargestArea(vector<int> &heights) {
    int n = heights.size();
	int largestArea = 0;
	for (int i = 0; i < n; i++) {
		int currentArea, height = heights[i];
		for (int j = i; j < n; j++) {
			height = min(height, heights[j]);
			currentArea = (j - i + 1) * height;
			largestArea = max(largestArea, currentArea);
		}
	}
	return largestArea;
}

Java

class Solution {
	int getLargestArea(int[] heights) {
	    int n = heights.length;
		int largestArea = 0;
		for (int i = 0; i < n; i++) {
			int currentArea, height = heights[i];
			for (int j = i; j < n; j++) {
				height = Math.min(height, heights[j]);
				currentArea = (j - i + 1) * height;
				largestArea = Math.max(largestArea, currentArea);
			}
		}
		return largestArea;
	}
}

Optimal Approach

The problem can be solved efficiently with a stack implementation.

• Create an empty stack say index to store the indices.
• Traverse the array and for each index i, while the stack is non-empty and heights[i] is less than the current top value in the stack. Remove that value from the stack and store it in prevIndx.
• Calculate the area taking heights[prevIndx] as height, index.top() as left index and i as the right index and update the maximum area.
• Insert the current index in the stack.
• If the stack is not empty after the traversal. Remove elements one by one from the stack and calculate the area. Keep updating the maximum area.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int getLargestArea(vector<int> &heights) {
    int n  = heights.size();
	stack<int> index;
	int largestArea = 0;
	for (int i = 0; i < n; i++) {
		while (!index.empty() && heights[index.top()] > heights[i]) {
			int prevIndx = index.top();
			index.pop();
			if (index.empty()) {
				int currentArea = i * heights[prevIndx];
				largestArea = max(largestArea, currentArea);
			} else {
				int currentArea = (i - 1 - index.top()) * heights[prevIndx];
				largestArea = max(largestArea, currentArea);
			}
		}
		index.push(i);
	}
	while(!index.empty()) {
		int prevIndx = index.top();
		index.pop();
		if (index.empty()) {
			int currentArea = n * heights[prevIndx];
			largestArea = max(largestArea, currentArea);
		} else {
			int currentArea = (n - 1 - index.top()) * heights[prevIndx];
			largestArea = max(largestArea, currentArea);
		}
	}
	return largestArea;
}

Java

class Solution {
	int getLargestArea(int[] heights) {
	    int n  = heights.length;
		Stack<Integer> index = new Stack<> ();
		int largestArea = 0;
		for (int i = 0; i < n; i++) {
			while (!index.isEmpty() && heights[index.peek()] > heights[i]) {
				int prevIndx = index.peek();
				index.pop();
				if (index.isEmpty()) {
					int currentArea = i * heights[prevIndx];
					largestArea = Math.max(largestArea, currentArea);
				} else {
					int currentArea = (i - 1 - index.peek()) * heights[prevIndx];
					largestArea = Math.max(largestArea, currentArea);
				}
			}
			index.push(i);
		}
		while(!index.isEmpty()) {
			int prevIndx = index.peek();
			index.pop();
			if (index.isEmpty()) {
				int currentArea = n * heights[prevIndx];
				largestArea = Math.max(largestArea, currentArea);
			} else {
				int currentArea = (n - 1 - index.peek()) * heights[prevIndx];
				largestArea = Math.max(largestArea, currentArea);
			}
		}
		return largestArea;
	}
}