python | from n^4 to n^3 to n^2
Goal: explain approach from n^4 to n^3 to n^2\n\nn^4\n- we start creating a rectangle at any given point in matrix -> o(n^2)\n- so at this given point we check 
**Goal**: explain approach from n^4 to n^3 to n^2\n\n**n^4**\n- we start creating a rectangle at any given point in matrix -> o(n^2)\n- so at this given point we check each row below it and see if the # of consecutive \'1\'s in each row gives us a new `minWidth` to consider\n- then update `maxArea` according to this `minWidth`\n- this approach has ideas similar to max stock price profit problem\n```\nclass Solution(object):\n    def maximalRectangle(self, matrix):\n        maxVal = 0\n        out = 0\n        minWidth = defaultdict(int)\n        for i in range(len(matrix)-1,-1,-1):\n            for j in range(len(matrix[0])-1, -1, -1):\n                minW = len(matrix[0])-j\n                maxArea = 0\n                for di in range(i, len(matrix)):\n                    currW = len(matrix[0])-j\n                    for dj in range(j,len(matrix[0])):\n                        if matrix[di][dj] != "1":\n                            currW=dj-j\n                            break\n                    minW = min(minW, currW)\n                    maxArea = max(maxArea, (di-i+1)*minW)\n                out = max(out, maxArea)\n        return out\n```\n\n**n^3**\n- we can preprocess the `minWidth` beforehand\n- if the `matrix[i][j+1]` is "1" and `matrix[i][j]` is \'1\' then just add `minWidth[i][j+1] + 1` to `matrix[i][j]` else it remains 0\n```\nclass Solution(object):\n    def maximalRectangle(self, matrix):        \n        maxVal = 0\n        out = 0\n        minWidth = defaultdict(int)\n        for di in range(len(matrix)):\n            currW = len(matrix[0])\n            for dj in range(len(matrix[0])-1, -1, -1):\n                if matrix[di][dj] != "1":\n                    minWidth[(di,dj)] = 0\n                else:\n                    minWidth[(di,dj)] = 1\n                    minWidth[(di,dj)] += minWidth[(di,dj+1)] if dj+1!=len(matrix[0]) else 0\n\n        \n        for i in range(len(matrix)-1,-1,-1):\n            for j in range(len(matrix[0])-1, -1, -1):\n                minW = len(matrix[0])-j\n                maxArea = 0\n                for di in range(i, len(matrix)):\n                    minW = min(minW, minWidth[(di,j)])\n                    maxArea = max(maxArea, (di-i+1)*minW)\n                out = max(out, maxArea)\n        return out\n```\n\n**n^2**\n- the last optimization to consider is that instead of using the o(1) extra space `maxArea`, we can use o(n) extra space with `maxLeft`, `maxRight`, and `stack` to do one less loop\n- we consider that at each column `j`:\n- one row\'s `maxWidth[i][j]` to be the max width\n\t- that means anything greater than this can still be considered in the rectangle\'s area\n\t- anything less than this will bound the rectangle we\'re considering\n\t- area = `minWidth[i][j]` * distance btwn the two bounding rows\n- this operation can be implemented using the `stack` data structure\n- this approach is very similar to the largest rectangle in histogram problem\n```\nclass Solution(object):\n    def maximalRectangle(self, matrix):\n        maxVal = 0\n        out = 0\n        if matrix==[]:\n            return 0\n        minWidth = defaultdict(lambda: defaultdict(int))\n        for di in range(len(matrix)):\n            currW = len(matrix[0])\n            for dj in range(len(matrix[0])-1, -1, -1):\n                if matrix[di][dj] != "1":\n                    minWidth[di][dj] = 0\n                else:\n                    minWidth[di][dj] = 1\n                    minWidth[di][dj] += minWidth[di][dj+1] if dj+1!=len(matrix[0]) else 0\n\t\t\t\t\t\n        maxArea = 0\n        for j in range(len(matrix[0])):\n            maxLeft = [-1]*len(matrix)\n            maxRight = [len(matrix)]*len(matrix)\n            stack = []\n            for i in range(len(matrix)):\n                while stack and minWidth[i][j] < minWidth[stack[-1]][j]:\n                    maxRight[stack.pop()] = i\n                maxLeft[i] = stack[-1] if stack else -1\n                stack.append(i)\n            area = [(maxRight[i] - maxLeft[i] - 1)*minWidth[i][j] for i in range(len(matrix))]\n            maxArea = max(maxArea, max(area))\n        return maxArea\n```    \n            \n
['Dynamic Programming', 'Stack', 'Python']