Jobs

Interviews

Discussions

Largest Rectangle in Histogram

Hard

Google

2 views

Topics:

ArraysStacks

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.

For example:

Consider the histogram with heights [2, 1, 5, 6, 2, 3]. The largest rectangle has an area of 10 (height 5, width 2, between indices 2 and 3).

Another example:

Consider the histogram with heights [2, 4]. The largest rectangle has an area of 4 (height 2, width 2).

Can you devise an algorithm to efficiently find the largest rectangular area in a given histogram?

Constraints:

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Largest Rectangle in Histogram

Hard

Google

2 views

Topics:

ArraysStacks

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.

For example:

Consider the histogram with heights [2, 1, 5, 6, 2, 3]. The largest rectangle has an area of 10 (height 5, width 2, between indices 2 and 3).

Another example:

Consider the histogram with heights [2, 4]. The largest rectangle has an area of 4 (height 2, width 2).

Can you devise an algorithm to efficiently find the largest rectangular area in a given histogram?

Constraints:

1 <= heights.length <= 10^5
0 <= heights[i] <= 10^4

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the heights in the `heights` array? Could they be zero or negative?
What is the maximum possible length of the `heights` array?
If the `heights` array is empty, what should I return?
Is the input `heights` array guaranteed to be valid (i.e., no null or undefined values)?
If there are multiple rectangles with the same maximum area, should I return the area of any of them?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible rectangle that could exist within the histogram. We essentially look at every possible width and height combination that the histogram allows and determine the rectangle's area. By comparing all of these areas, we can find the largest one.

Here's how the algorithm would work step-by-step:

Consider each bar in the histogram as the potential right edge of a rectangle.
For each of those bars, go backward, one bar at a time, towards the left edge of the histogram.
At each step backward, find the shortest bar between the left and right edges of the current rectangle (this shortest bar determines the height of the rectangle).
Calculate the area of the rectangle using the distance between the right and left edges as the width, and the height found previously.
Compare the calculated area with the largest area we've found so far.
If the calculated area is larger than the current largest area, replace the current largest area with the new one.
Repeat the above process for every possible starting bar on the right edge to explore all possible rectangle combinations.
Once all possibilities have been checked, the largest area found is the answer.

Code Implementation

def largest_rectangle_in_histogram_brute_force(heights):
    largestArea = 0
    numberOfBars = len(heights)

    for rightEdge in range(numberOfBars):
        # Each bar considered as right edge

        for leftEdge in range(rightEdge, -1, -1):

            minimumHeight = heights[leftEdge]
            for currentBar in range(leftEdge, rightEdge + 1):
                #Find shortest bar, height of rectangle
                minimumHeight = min(minimumHeight, heights[currentBar])

            width = rightEdge - leftEdge + 1
            area = minimumHeight * width

            # Check if the area is the largest
            if area > largestArea:
                largestArea = area

    return largestArea

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n bars in the histogram, considering each bar as a potential right edge of a rectangle. The inner loop, for each right edge, iterates backwards towards the left edge, potentially examining all bars to the left of the current right edge. In the worst case, this inner loop also runs up to n times. Therefore, the nested loops lead to approximately n * n operations, simplifying to O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through the input histogram represented by the array of heights. It only uses a few scalar variables like loop counters, temporary height and area values, and a variable to keep track of the largest area found so far. The number of such variables remains constant irrespective of the input size, denoted as N. Therefore, the space complexity is constant.

Optimal Solution

Approach

The goal is to find the biggest rectangular area within a histogram. We use a clever technique to keep track of potential rectangles, building them up as we go and figuring out their area when we find a boundary.

Here's how the algorithm would work step-by-step:

Imagine you're walking across the histogram from left to right.
Keep track of the bars that could potentially form the bottom of a rectangle.
As you move, if you find a bar that's shorter than the previous one, it means you've found the end of a potential rectangle.
When you find the end, calculate the area of that rectangle using the height of the shortest bar within that range and the width of the range.
Compare the calculated area with the current largest area, and update if needed.
Keep going until you reach the end of the histogram, and you'll have the largest rectangle area.

Code Implementation

def largestRectangleArea(heights):
    max_area = 0
    stack = []
    heights_length = len(heights)

    for i in range(heights_length + 1):
        # Add a zero to the end to pop all elements in the stack
        while stack and (i == heights_length or heights[stack[-1]] > heights[i]):
            height = heights[stack.pop()]
            # Calculate width, if stack is empty, width starts from 0
            if stack:
                width = i - stack[-1] - 1
            else:
                width = i

            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area

Big(O) Analysis

Time Complexity

O(n) – The provided approach uses a stack to keep track of potential rectangles. We iterate through the histogram bars once. While iterating, we might push a bar onto the stack or pop bars from the stack if we encounter a shorter bar. Each bar is pushed onto the stack and popped from the stack at most once. Therefore, the number of push and pop operations are bounded by 2n. Calculating the area during the pop operation takes constant time. As a result, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses a stack to keep track of bars that could potentially form the bottom of a rectangle. In the worst-case scenario, where the histogram bars are continuously increasing, all N bars could be pushed onto the stack. Therefore, the auxiliary space used by the stack grows linearly with the number of bars in the histogram. The space complexity is thus O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no rectangle can be formed.
Input array with a single element	Return the value of the single element as the area.
Input array with all elements being zero	Return 0, as the largest possible rectangle area is 0.
Input array with all elements being identical and non-zero	The largest rectangle area will be the value of the element multiplied by the array length.
Input array sorted in ascending order	The algorithm should correctly calculate areas based on heights multiplied by varying widths.
Input array sorted in descending order	The algorithm correctly handles monotonically decreasing histograms.
Large input array to test for time complexity	A stack-based approach should have O(n) time complexity.
Input array containing very large integer values, potentially leading to integer overflow when calculating area	Use a larger data type (long) for area calculations to prevent overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the heights in the `heights` array? Could they be zero or negative?
What is the maximum possible length of the `heights` array?
If the `heights` array is empty, what should I return?
Is the input `heights` array guaranteed to be valid (i.e., no null or undefined values)?
If there are multiple rectangles with the same maximum area, should I return the area of any of them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each bar in the histogram as the potential right edge of a rectangle.
For each of those bars, go backward, one bar at a time, towards the left edge of the histogram.
At each step backward, find the shortest bar between the left and right edges of the current rectangle (this shortest bar determines the height of the rectangle).
Calculate the area of the rectangle using the distance between the right and left edges as the width, and the height found previously.
Compare the calculated area with the largest area we've found so far.
If the calculated area is larger than the current largest area, replace the current largest area with the new one.
Repeat the above process for every possible starting bar on the right edge to explore all possible rectangle combinations.
Once all possibilities have been checked, the largest area found is the answer.

Code Implementation

def largest_rectangle_in_histogram_brute_force(heights):
    largestArea = 0
    numberOfBars = len(heights)

    for rightEdge in range(numberOfBars):
        # Each bar considered as right edge

        for leftEdge in range(rightEdge, -1, -1):

            minimumHeight = heights[leftEdge]
            for currentBar in range(leftEdge, rightEdge + 1):
                #Find shortest bar, height of rectangle
                minimumHeight = min(minimumHeight, heights[currentBar])

            width = rightEdge - leftEdge + 1
            area = minimumHeight * width

            # Check if the area is the largest
            if area > largestArea:
                largestArea = area

    return largestArea

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're walking across the histogram from left to right.
Keep track of the bars that could potentially form the bottom of a rectangle.
As you move, if you find a bar that's shorter than the previous one, it means you've found the end of a potential rectangle.
When you find the end, calculate the area of that rectangle using the height of the shortest bar within that range and the width of the range.
Compare the calculated area with the current largest area, and update if needed.
Keep going until you reach the end of the histogram, and you'll have the largest rectangle area.

Code Implementation

def largestRectangleArea(heights):
    max_area = 0
    stack = []
    heights_length = len(heights)

    for i in range(heights_length + 1):
        # Add a zero to the end to pop all elements in the stack
        while stack and (i == heights_length or heights[stack[-1]] > heights[i]):
            height = heights[stack.pop()]
            # Calculate width, if stack is empty, width starts from 0
            if stack:
                width = i - stack[-1] - 1
            else:
                width = i

            max_area = max(max_area, height * width)

        stack.append(i)

    return max_area

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no rectangle can be formed.
Input array with a single element	Return the value of the single element as the area.
Input array with all elements being zero	Return 0, as the largest possible rectangle area is 0.
Input array with all elements being identical and non-zero	The largest rectangle area will be the value of the element multiplied by the array length.
Input array sorted in ascending order	The algorithm should correctly calculate areas based on heights multiplied by varying widths.
Input array sorted in descending order	The algorithm correctly handles monotonically decreasing histograms.
Large input array to test for time complexity	A stack-based approach should have O(n) time complexity.
Input array containing very large integer values, potentially leading to integer overflow when calculating area	Use a larger data type (long) for area calculations to prevent overflow.