O(n ^ 2) solution based on histogram solution in C# for reference


  • 1
    A

    This took me a while to figure out when I tried this for the first time. I had to understand and code up https://leetcode.com/problems/largest-rectangle-in-histogram/ (thanks to other comments in the discussion forum!) before I attempted this one again.

    The idea is each time you iterate through a row in input matrix, keep track of the heights in a separate array (which is your histogram input). After you go through a row, calculate the maximum area for that histogram and compare it with current maximum and update it if necessary.

    For example: 
    1 1 0 1
    0 0 1 0 
    
    After iterating though row 1, your histogram = [1 1 0 1], current Area = 2 and so maxArea = 2
    After iterating though row 2, your histogram = [0 0 1 0], current Area = 1 and so maxArea = 2
    
    // O(n)
    private int getMaxRectangleArea(int[] heights) {
        int maxArea = 0;
        
        Stack<int> rectHeights = new Stack<int>();
        
        int current = 0;
        while(current < heights.Length) {
            if (rectHeights.Count == 0 || heights[rectHeights.Peek()] <= heights[current]) {
                rectHeights.Push(current++);
            } else {
                int currHeightIndex = rectHeights.Pop();
                int areaWithTop = heights[currHeightIndex] * 
                    (rectHeights.Count == 0 ? current : current - 1 - rectHeights.Peek());
                maxArea = Math.Max(maxArea, areaWithTop);
            }
        }
        
        while (rectHeights.Count > 0) {
            int currHeightIndex = rectHeights.Pop();
            int areaWithTop = heights[currHeightIndex] * (rectHeights.Count == 0 ? current : current - 1 - rectHeights.Peek());
            maxArea = Math.Max(maxArea, areaWithTop);
        }
        
        return maxArea;
    }
    
    // O(n ^ 2)
    public int MaximalRectangle(char[,] matrix) {
        int[] heights = new int[matrix.GetLength(1)]; 
        int maxArea = 0;
        
        for(int row = 0; row < matrix.GetLength(0); row++) {
            for(int column = 0; column < matrix.GetLength(1); column++) {
                if (matrix[row, column] == '1') { 
                        heights[column]++;
                } else if (matrix[row, column] == '0') {
                    heights[column] = 0;
                }
            }
            
            maxArea = Math.Max(maxArea, getMaxRectangleArea(heights));
        }
        
        return maxArea;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.