Largest Rectangle in Histogram

Hard

Amazon

1 view

Topics:

ArraysStacks

You are given an array of integers heights representing a histogram where the width of each bar is 1. Your task is to find the area of the largest rectangle that can be fit within the histogram. Imagine you have a series of adjacent bars of varying heights, and you want to determine the biggest rectangular area you can form using these bars.

Here are some examples to illustrate the problem:

heights = [2, 1, 5, 6, 2, 3] In this case, the largest rectangle has an area of 10. It spans the bars of height 5 and 6.
heights = [2, 4] Here, the largest rectangle has an area of 4, formed by either the single bar of height 4, or the combination of both bars, where the height is limited by the shorter bar (height 2) times the width (2), resulting in 4.
heights = [6, 2, 5, 4, 5, 1, 6] In this histogram, the largest rectangle has an area of 12. It spans from the first bar (height 6) to the end of bar with height 1. Since the smallest height between them is bar of height 2. So you cannot find the largest rectangle from it.

Could you provide an algorithm to solve this problem efficiently? Consider the time and space complexity of your solution.

Largest Rectangle in Histogram

Hard

Amazon

1 view

Topics:

ArraysStacks

Here are some examples to illustrate the problem:

heights = [2, 1, 5, 6, 2, 3] In this case, the largest rectangle has an area of 10. It spans the bars of height 5 and 6.
heights = [2, 4] Here, the largest rectangle has an area of 4, formed by either the single bar of height 4, or the combination of both bars, where the height is limited by the shorter bar (height 2) times the width (2), resulting in 4.
heights = [6, 2, 5, 4, 5, 1, 6] In this histogram, the largest rectangle has an area of 12. It spans from the first bar (height 6) to the end of bar with height 1. Since the smallest height between them is bar of height 2. So you cannot find the largest rectangle from it.

Could you provide an algorithm to solve this problem efficiently? Consider the time and space complexity of your solution.

Solution

Largest Rectangle in Histogram

Problem Description

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.

Naive Approach

The brute force approach would be to consider every possible rectangle. For each starting bar, we iterate through all subsequent bars, considering the minimum height between them as the height of the rectangle, and the width as the number of bars considered so far. We keep track of the maximum area encountered.

Code (Python)

def largestRectangleArea_brute_force(heights):
    max_area = 0
    n = len(heights)
    for i in range(n):
        for j in range(i, n):
            min_height = min(heights[i:j+1])
            width = j - i + 1
            area = min_height * width
            max_area = max(max_area, area)
    return max_area

Time Complexity

O(n^2), where n is the number of bars in the histogram. This is due to the nested loops.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Approach: Using a Stack

The optimal approach uses a stack to keep track of the indices of increasing heights. When we encounter a bar with a height less than the bar at the top of the stack, it means we've found the right boundary for the rectangle defined by the bar at the top of the stack. We pop the stack and calculate the area of that rectangle.

Algorithm

Initialize an empty stack.
Iterate through the heights array:
- While the stack is not empty and the current height is less than the height at the index at the top of the stack:
  - Pop the top index from the stack.
  - Calculate the area of the rectangle formed by the popped height:
    - Height = height at the popped index.
    - Width = index - stack top - 1 (if stack is not empty), or index (if stack is empty).
  - Update max area if current area is greater.
- Push the current index onto the stack.
After iterating through all heights, if the stack is not empty, process remaining bars in the stack similarly.

Code (Python)

def largestRectangleArea(heights):
    max_area = 0
    stack = []
    n = len(heights)
    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1 if stack else i
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack:
        height = heights[stack.pop()]
        width = n - stack[-1] - 1 if stack else n
        max_area = max(max_area, height * width)

    return max_area

Time Complexity

O(n), where n is the number of bars in the histogram. Each bar is pushed onto and popped from the stack at most once.

Space Complexity

O(n), in the worst case, the stack can contain all the indices if the heights are in increasing order.

Edge Cases

Empty input: If the input heights array is empty, the largest area is 0.
All bars have the same height: The largest area is the height multiplied by the number of bars.
Heights are in increasing order: The stack will contain all indices until the end, requiring processing of the stack afterward.
Heights are in decreasing order: Each bar will cause pops from the stack, ensuring correct calculation of rectangle areas.

Solution

Largest Rectangle in Histogram

Problem Description

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.

Naive Approach

Code (Python)

def largestRectangleArea_brute_force(heights):
    max_area = 0
    n = len(heights)
    for i in range(n):
        for j in range(i, n):
            min_height = min(heights[i:j+1])
            width = j - i + 1
            area = min_height * width
            max_area = max(max_area, area)
    return max_area

Time Complexity

O(n^2), where n is the number of bars in the histogram. This is due to the nested loops.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Approach: Using a Stack

Algorithm

Initialize an empty stack.
Iterate through the heights array:
- While the stack is not empty and the current height is less than the height at the index at the top of the stack:
  - Pop the top index from the stack.
  - Calculate the area of the rectangle formed by the popped height:
    - Height = height at the popped index.
    - Width = index - stack top - 1 (if stack is not empty), or index (if stack is empty).
  - Update max area if current area is greater.
- Push the current index onto the stack.
After iterating through all heights, if the stack is not empty, process remaining bars in the stack similarly.

Code (Python)

def largestRectangleArea(heights):
    max_area = 0
    stack = []
    n = len(heights)
    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1 if stack else i
            max_area = max(max_area, height * width)
        stack.append(i)

    while stack:
        height = heights[stack.pop()]
        width = n - stack[-1] - 1 if stack else n
        max_area = max(max_area, height * width)

    return max_area

Time Complexity

O(n), where n is the number of bars in the histogram. Each bar is pushed onto and popped from the stack at most once.

Space Complexity

O(n), in the worst case, the stack can contain all the indices if the heights are in increasing order.

Edge Cases

Empty input: If the input heights array is empty, the largest area is 0.
All bars have the same height: The largest area is the height multiplied by the number of bars.
Heights are in increasing order: The stack will contain all indices until the end, requiring processing of the stack afterward.
Heights are in decreasing order: Each bar will cause pops from the stack, ensuring correct calculation of rectangle areas.