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.

Description Solution Video 17:20

84. Largest Rectangle in Histogram

Hard50.7% acceptance30 companies

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: