Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Solution

C# Program

public class Solution {
    public int MaximalRectangle(char[][] matrix) {
        
        if(matrix == null || matrix.Length == 0)
            return 0;
        
        int row = matrix.Length;
        int col = matrix[0].Length;
        
        int[] temp = new int[col];
        
        int maxArea = 0;
        
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(matrix[i][j] == '1')
                    temp[j] += 1;
                else 
                    temp[j] = 0;
            }
            
            maxArea = Math.Max(maxArea,LargestRectangleArea(temp));
        }
        return maxArea;
        
    }
    
    public int LargestRectangleArea(int[] heights) {
         
        Stack<int> stack = new Stack<int>();
        int maxArea = 0;
         
        int i = 0;
         
        for(i=0;i<heights.Length;i++)
        {
            int currentElement = heights[i];
             
            if(stack.Count == 0)
                stack.Push(i);
             
            else
            {
                int topElementInStack = heights[stack.Peek()];
                 
                if(topElementInStack <= currentElement)  
                {
                    stack.Push(i);
                }
                else
                {
                    //Pop stack until topElementInStack <= currentElement
                    while(stack.Count > 0 && heights[stack.Peek()] > currentElement)
                    {
                        int poppedElement = heights[stack.Pop()];
                         
                        //Find Area
                        if(stack.Count == 0)
                        {
                            int area = poppedElement * i;
                            maxArea = Math.Max(area,maxArea);
                        }
                        else
                        {
                            int area = poppedElement * (i - stack.Peek() - 1);    
                            maxArea = Math.Max(area,maxArea);
                        }
                    }
                     
                    stack.Push(i);
                }
            }
        }
         
        while(stack.Count > 0)
        {
            int poppedElement = heights[stack.Pop()];
             
            //Find Area
            if(stack.Count == 0)
            {
                int area = poppedElement * i;
                maxArea = Math.Max(area,maxArea);
                break;
            }
            else
            {
                int area = poppedElement * (i - stack.Peek() - 1);
                maxArea = Math.Max(area,maxArea);
            }
        }
        return maxArea;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s