We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Rectangle in Histogram

Number: 84

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, Microsoft, Uber, DoorDash, Apple, DE Shaw, Roblox, Zoho, Adobe, Zynga, Flipkart, Yahoo, Myntra

Problem Description

Given an array of integers representing the histogram’s bar heights (each bar has width 1), return the area of the largest rectangle that can be formed within the bounds of the histogram.

Key Insights

  • Each bar can potentially extend left and right as long as the neighboring bars are not shorter.
  • A monotonic (increasing) stack can be used to efficiently track indices of bars.
  • When encountering a bar lower than the one on the top of the stack, pop the stack and calculate the area of the rectangle formed with the popped bar height.
  • A dummy bar (of height 0) is appended at the end to ensure all bars are processed.

Space and Time Complexity

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

Solution

The solution employs a monotonic stack to traverse the histogram once. For each bar, while the current bar's height is less than the height at the top index of the stack, it pops from the stack and calculates the area using the popped height as the smallest bar. The width for the rectangle is determined by the difference between the current index and the index from the stack (or the current index if the stack is empty). This effectively finds the maximum rectangular area possible. A sentinel value (0) is added at the end of the histogram to flush any remaining bars from the stack.

Code Solutions

# Python solution

def largestRectangleArea(heights):
    # Append a zero to flush out the remaining bars in the stack
    heights.append(0)
    stack = []  # Stack to store indices of bars
    max_area = 0
    
    # Iterate over each index and bar height
    for i, h in enumerate(heights):
        # Process bars that are taller than the current bar
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]  # Height of the bar at the index popped from the stack
            # Calculate width: if stack is empty, width is the current index; otherwise, it's the difference
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    
    return max_area

# Example usage:
if __name__ == "__main__":
    histogram = [2, 1, 5, 6, 2, 3]
    print(largestRectangleArea(histogram))
← Back to All Questions