using max area of histofgram
This guy deserves an appluase for a fabulous explanation ! (video in Hindi)\n\nhttps://www.youtube.com/watch?v=St0Jf_VmG_g&list=PL_z_8CaSLPWdeOezg68SKkeLN4-T_jN
This guy deserves an appluase for a fabulous explanation ! (video in Hindi)\n\nhttps://www.youtube.com/watch?v=St0Jf_VmG_g&list=PL_z_8CaSLPWdeOezg68SKkeLN4-T_jNHd&index=8\n\n```\nclass Solution:\n    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n        \n        if not matrix:\n            return 0\n        \n        prev = [0]*len(matrix[0])\n        max_area = 0\n        for row in matrix:\n            curr_row = [int(i) for i in row]\n            for j in range (len(curr_row)):\n                curr_row[j] = curr_row[j] + prev[j] if curr_row[j] !=0 else 0\n            max_area = max(max_area, self.largestRectangleArea(curr_row))\n            prev = curr_row\n            \n        return max_area\n                \n            \n    \n    #largest ares of a histogram !!\n    def largestRectangleArea(self, heights):      \n\n        def get_small_r(heights):\n            stack_r = []\n            sm_r = [0] * len(heights)\n            for j in range(len(heights) - 1, -1 , -1):\n\n                while stack_r and heights[stack_r[-1]] >= heights[j]:\n                    stack_r.pop()\n\n                if(not stack_r):\n                    sm_r[j] = -1\n                else:\n                    sm_r[j] = stack_r[-1]\n                stack_r.append(j) \n            return sm_r\n\n        def get_small_l(heights):\n            stack_l = []\n            sm_l = [None] * len(heights)\n            for j in range(len(heights)):\n                while stack_l and heights[stack_l[-1]] >= heights[j]:\n                    stack_l.pop()\n                if(not stack_l):\n                    sm_l[j] = -1\n                else:\n                    sm_l[j] = stack_l[-1]\n                stack_l.append(j) \n            return sm_l\n\n        max_area = 0\n        stack_l = get_small_l(heights)\n        stack_r = get_small_r(heights)\n        \n        for j in range (len(heights)):\n            l = j - stack_l[j] -1 if stack_l[j] != -1 else j\n            r = stack_r[j] -1 -j  if stack_r[j] != -1 else len(heights) - j -1\n            t = 1 + l + r \n            max_area = max(max_area,   heights[j] *t )\n        return max_area\n\n```
[]