Java solution using finding area of a histogram method


  • 0
    S
    public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0)
            return 0;
            
        int len = matrix[0].length;
       // This array represent the histogram after going through each row.
        int[] arr = new int[len];
        Arrays.fill(arr,0);
        int max =0;
        
        for(int i =0; i < matrix.length; i++)
        {
            for(int j =0; j < len; j++)
            {
                if(matrix[i][j] == '1')
                {
                    arr[j] += 1;
                }
                else
                {
                    arr[j] =0;
                }
            }
            max = Math.max(max, calcuateArea(arr));
        }
        return max;
    }
    

    /*
    Step 1: Add index to the stack if the value at that current index is greater than or equal to the value at index which is at the top of the stack

    Step 2: if condition in step 1 does not satisfy then remove indices from the stack till above condition holds or stack is empty

    Step 3: While removing from the stack use the following formula for area calculation:
    if(stack.isEmpty)
    area = arr[top]i
    else
    area = arr[top]
    (i - stack.peek()-1)

    Refer: tushar roy's video on calculating area of a histogram: https://www.youtube.com/watch?v=ZmnqCZp9bBs
    */

     private int calcuateArea(int[] arr)
    {
        int top =0;
        int area =0;
        int maxarea = 0;
        Stack<Integer> stak = new Stack<>();
        int i =0;
        stak.push(i);
        for(i =1; i < arr.length; i++)
        {
            if(arr[i] < arr[(int)stak.peek()])
            {
                while(!stak.isEmpty() && arr[(int)stak.peek()] > arr[i])
                {
                    top = (int)stak.pop();
                    if(stak.isEmpty())
                    {
                        area = arr[top]*i;
                    }
                    else
                    {
                        area = arr[top]*(i-(int)stak.peek()-1);
                    }
                    if(area > maxarea)
                        maxarea = area;
                }
            }
              stak.push(i);
        }
        while(!stak.isEmpty())
        {
            top = (int)stak.pop();
                if(stak.isEmpty())
                {
                    area = arr[top]*i;
                }
                else
                {
                    area = arr[top]*(i-(int)stak.peek()-1);
                }
                if(area > maxarea)
                    maxarea = area;
        }
        return maxarea;
    }
    }

Log in to reply
 

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