Solution For Largest Rectangle In Histogram

Problem Statement:

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, find the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3] Output: 10
Explanation: The height of the largest rectangle is 5 and the width is 2, so the area is 5 * 2 = 10.

Example 2:

Input: heights = [2,4] Output: 4

Solution:

We can solve this problem by using the concept of stack. The intuition is to traverse through the heights array and for each height, we want to find the maximum area rectangle with this height as the smallest bar. To do that, we will use a stack to maintain left and right boundaries of the rectangle.

1. Initialize an empty stack and a variable called max_area to store the maximum area. Then iterate through the input array, heights.

2. For each height i, if the stack is empty or the current height is greater than or equal to the height at the top of the stack, push the current index i onto the stack.

3. If the current height is less than the height at the top of the stack, pop the top of the stack and calculate the area of the rectangle with the popped height as the smallest bar.

4. The width of the rectangle is the current index i minus the index at the top of the stack minus 1 (since we popped the top of the stack).

5. The height of the rectangle is the popped height.

6. Calculate the area of the rectangle by multiplying the height by the width.

7. Update the max_area variable if the area of the current rectangle is greater than the current max_area.

8. Repeat steps 3-7 until the current height is greater than or equal to the height at the top of the stack.

9. Push the current index i onto the stack.

10. After iterating through the entire input array, repeat steps 3-7 for each remaining element on the stack until the stack is empty.

11. Return max_area.

Code:

Step by Step Implementation For Largest Rectangle In Histogram

class Solution {
    public int largestRectangleArea(int[] heights) {
        // This is a stack-based solution to the largest rectangle in histogram problem.
        // We maintain a stack of rectangles, where each rectangle is represented by
        // its height. We add rectangles to the stack if they are taller than the
        // rectangle at the top of the stack, or if they are the same height as the
        // rectangle at the top of the stack and the stack size is 1. Otherwise, we
        // keep popping rectangles off the stack until we find a rectangle that is
        // taller than the one we are trying to add, at which point we add the
        // new rectangle with the height of the popped rectangle as its height.
        
        // We also keep track of the maximum rectangle area while we are processing
        // the rectangles.
        
        Stack stack = new Stack<>();
        int maxArea = 0;
        
        for (int i = 0; i <= heights.length; i++) {
            // We add a sentinel value of 0 at the end of the array to make sure
            // that we process all the rectangles in the stack.
            int h = (i == heights.length ? 0 : heights[i]);
            
            if (stack.isEmpty() || h >= heights[stack.peek()]) {
                // We push the index of the rectangle onto the stack if the stack
                // is empty or if the height of the rectangle we are processing
                // is greater than or equal to the height of the rectangle at the
                // top of the stack.
                stack.push(i);
            } else {
                // We keep popping rectangles off the stack until we find a
                // rectangle whose height is greater than the height of the
                // rectangle we are processing. We then calculate the area of
                // the popped rectangle, update the maximum area if necessary,
                // and push the index of the rectangle we are processing onto
                // the stack.
                int top = stack.pop();
                int area = heights[top] * (stack.isEmpty() ? i : i - 1 - stack.peek());
                maxArea = Math.max(maxArea, area);
                i--;
            }
        }
        
        return maxArea;
    }
}

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # We will use a stack to keep track of the rectangles
        stack = []
        max_area = 0
        
        # Iterate over the height array
        for i in range(len(heights)):
            # If the stack is empty or the current height is greater than the height of the last element in the stack
            if not stack or heights[i] >= heights[stack[-1]]:
                # Append the current height to the stack
                stack.append(i)
            # If the current height is less than the height of the last element in the stack
            else:
                # This is where we calculate the max area
                # We pop the last element in the stack and calculate the area with it
                # First, we find the index of the last element in the stack which is also the start index of the current rectangle
                start_index = stack.pop()
                # If the stack is empty, then the current rectangle extends to the end of the array
                if not stack:
                    end_index = i
                # Otherwise, the current rectangle extends to the index before the start index of the next rectangle
                else:
                    end_index = i - 1
                # To calculate the area, we need to find the width and height
                # The width is simply the difference between the end and start index + 1
                width = end_index - start_index + 1
                # The height is the value at the current height index
                height = heights[start_index]
                # We calculate the area and compare it to the max area
                area = width * height
                max_area = max(max_area, area)
        # After we have iterated through the entire array, we need to check if there are any remaining rectangles
        # To do this, we simply iterate through the stack until it is empty
        while stack:
            # We pop the last element in the stack and calculate the area with it
            # First, we find the index of the last element in the stack which is also the start index of the current rectangle
            start_index = stack.pop()
            # If the stack is empty, then the current rectangle extends to the end of the array
            if not stack:
                end_index = len(heights)
            # Otherwise, the current rectangle extends to the index before the start index of the next rectangle
            else:
                end_index = len(heights) - 1
            # To calculate the area, we need to find the width and height
            # The width is simply the difference between the end and start index + 1
            width = end_index - start_index + 1
            # The height is the value at the current height index
            height = heights[start_index]
            # We calculate the area and compare it to the max area
            area = width * height
            max_area = max(max_area, area)
            
        # Return the max area
        return max_area

var largestRectangleArea = function(heights) {
    let maxArea = 0;
    
    for (let i = 0; i < heights.length; i++) {
        let minHeight = heights[i];
        
        for (let j = i; j < heights.length; j++) {
            minHeight = Math.min(minHeight, heights[j]);
            maxArea = Math.max(maxArea, minHeight * (j - i + 1));
        }
    }
    
    return maxArea;
};

The problem is to find the largest rectangle in a histogram, where the histogram is a list of heights of rectangles.

One solution is to use a stack to keep track of the rectangles. We can push the rectangles onto the stack in order of height. When we find a rectangle that is taller than the one on top of the stack, we know that the rectangle on top of the stack is not part of the largest rectangle. We can then pop the rectangles off the stack until we find a rectangle that is taller than the one on top of the stack. We can then push the new rectangle onto the stack. We can continue this until we have processed all the rectangles.

The largest rectangle will be the one that is tallest and has the widest width. We can keep track of the width by keeping track of the number of rectangles in the stack. The width will be the number of rectangles in the stack multiplied by the height of the rectangle on the top of the stack.

#include  #include  using namespace std; int largestRectangleArea(vector& heights) { int maxArea = 0; stack st; for (int i = 0; i <= heights.size(); i++) { int h = (i == heights.size() ? 0 : heights[i]); if (st.empty() || h >= heights[st.top()]) { st.push(i); } else { int top = st.top(); st.pop(); maxArea = max(maxArea, heights[top] * (st.empty() ? i : i - st.top() - 1)); i--; } } return maxArea; }

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        //This is a brute force solution that checks every possible rectangle
        //in the histogram.
        
        //We start at the leftmost bar and consider every possible rectangle
        //that has this bar as the leftmost bar. To do this, we iterate from
        //the left to the right, keeping track of the height of the current bar
        //and the width of the rectangle.
        
        //When we encounter a bar that is shorter than the current one, we know
        //that any rectangle that includes that bar will have a height that is
        //at most the height of the current bar. Therefore, we can update our
        //running maximum area to be the maximum of the current area and the
        //area of the rectangle with height equal to the current bar's height
        //and width equal to the difference between the current bar's index and
        //the index of the first bar that is shorter than the current one.
        
        int maxArea = 0;
        for(int i = 0; i < heights.Length; i++) {
            int height = heights[i];
            int width = 1;
            
            //Iterate to the right, keeping track of the width
            for(int j = i+1; j < heights.Length; j++) {
                //If the height of the bar at index j is less than the height
                //of the bar at index i, we update the width and break out of
                //the loop.
                if(heights[j] < height) {
                    width = j - i;
                    break;
                }
            }
            
            //If we never broke out of the loop, that means that all the bars
            //from index i to the end of the array had heights greater than or
            //equal to the height of the bar at index i. Therefore, we can just
            //set the width to be the difference between the end of the array
            //and the starting index.
            if(width == 1) {
                width = heights.Length - i;
            }
            
            //Update the maximum area
            maxArea = Math.Max(maxArea, height * width);
        }
        
        return maxArea;
    }
}