How do you solve Largest Rectangle in Histogram on LeetCode?

Largest Rectangle in Histogram (LeetCode #84) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The largest rectangle can be formed using each bar as the shortest bar.

What is the brute force solution for Largest Rectangle in Histogram?

The brute force approach for Largest Rectangle in Histogram is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible rectangle that can be formed in the histogram. For each bar, it calculates the maximum rectangle that can be formed using that bar as the shortest bar in the rectangle. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Largest Rectangle in Histogram?

Largest Rectangle in Histogram uses the following concepts: Array, Stack, Monotonic Stack. The recommended patterns to study are: Stack, Monotonic Stack.

What are the interview tips for Largest Rectangle in Histogram?

Understand the problem visually; draw the histogram. Practice explaining your thought process while coding. Be prepared to discuss time and space complexity.

What are common mistakes when solving Largest Rectangle in Histogram?

Not handling edge cases like empty arrays or arrays with only one bar. Confusing the width calculation when popping from the stack.

#84

Largest Rectangle in Histogram

Hard

ArrayStackMonotonic StackStackMonotonic Stack

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a stack to efficiently calculate the largest rectangle area. It leverages the fact that we can determine the width of the rectangle for each bar by keeping track of the indices of the bars in a stack.

⚙️

Algorithm

5 steps

1Step 1: Initialize a stack and a variable max_area to 0.
2Step 2: Iterate through each bar in the heights array, using an index.
3Step 3: While the stack is not empty and the current height is less than the height at the index stored at the top of the stack, pop from the stack and calculate the area using the popped height as the shortest bar.
4Step 4: Push the current index onto the stack.
5Step 5: After iterating through the heights, pop any remaining indices in the stack and calculate the area.

solution.py16 lines

1# Full working Python code
2
3def largestRectangleArea(heights):
4    stack = []
5    max_area = 0
6    heights.append(0)  # Append a zero height to pop all remaining bars
7    for i in range(len(heights)):
8        while stack and heights[i] < heights[stack[-1]]:
9            h = heights[stack.pop()]
10            w = i if not stack else i - stack[-1] - 1
11            max_area = max(max_area, h * w)
12        stack.append(i)
13    return max_area
14
15# Example usage
16print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

ℹ

Complexity note: The time complexity is O(n) because each bar is pushed and popped from the stack at most once. The space complexity is O(n) due to the stack used for storing indices.

1The largest rectangle can be formed using each bar as the shortest bar.
2Using a stack allows us to efficiently calculate the width of rectangles.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.