[Python3] Faster than 100% - Easy [Explanation + Comments]
The core logic of my program is :\nFor any cell (i,j) for all cells in the same row store the number of ones starting from that row.\nFor example, matrix = [[0,
The core logic of my program is :\nFor any cell (i,j) for all cells in the same row store the number of ones starting from that row.\nFor example, matrix = [[0,0,1],[1,1,1],[1,0,1]]\nCorresponding map (d) = {1: [2,1,2], 2: [1,1], 0: [3]}\nExplanation of map: \nKey corresponds to the row number. \nLet\'s look at row number 0, \n* for column 2 - 3 ones\n\nLet\'s look at row number 1, \n* for column 0 - 2 ones\n* for column 1 - 2 ones\n* for column 2 - 1 one\n\nLet\'s look at row number 2, \n* for column 0 - 1 one\n* for column 1 - 1 one\n \nNow that we have the map constructed, we will use this map to find the maximum size submatrix.\n\nTo find the maximum size submatrix, we will sort list for each key in the descending order and find the maximum height possible (minimum of the list till that index) for the particular width.\nMaximum size = Area = height x width\nLet look at row number 1:\n[2,1,2]\nSorted list = [2,2,1]\n* for width = 1\n\theight = min([2])\n\tArea = min([2])x1 = 2\n\t\n* for width = 2\n\theight = min([2,2])\n\tArea = min([2,2]) x 2 = 4\n\n* for width = 3\n\theight = min([2,2,1]) = 1\n\tArea = min([2,2,1]) x 2 = 2\n\t\n\tSimilarly, area will be calculated for row number 0 and 2. Maximum area = 4\n\t\nRunning time : O(mn<sup>2</sup>log<sub>2</sub>(n))\n\n```\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        d = {}  # dictionary storing row number and corresponding list of the number of ones\n        m, n = len(matrix), len(matrix[0])\n        \n        for col in range(n):               # for each column\n            start = -1      # start is initialized to -1, when we will encounter streak ones  it will be initialized\n            \n            for row in range(m):\n                if matrix[row][col]:        # when the cell contains 1\n                    if start == -1:         # when the first one is encountered\n                        start = row         # set start to the row number \n                else:                       # when the cell contains a 0\n                    if start!=-1:           # if there was a streak ones encountered before\n                        end = row\n                        for row_index in range(start, end):  \n                        # iterate over the beginning of the streak till the end\n\t\t\t\t\t\t# for each row index in the streak assign the key to be row index and the corresponding length of streak starting from that point.\n                        \n                            if row_index not in d:     # if the row index is not present in the dictionary\n                                d[row_index] = []      # create an empty list for the row index\n                                \n                            d[row_index].append(end - row_index)    # append the length of the streak from the row index\n                            \n                    start = -1                        # re-initialize start to -1 as the streak is over\n    \n            if start!=-1:  # if the column has ended but the streak was present uptil the end\n\t\t\t# repeat the same process we did above with an exception, end = m\n                end = m\n                for row_index in range(start, end):\n                    if row_index not in d:\n                        d[row_index] = []\n                    d[row_index].append(end - row_index)\n        \n\t\t## finding the max area\n        area = 0                                   # initialize area to be 0\n        for key in d:                              # for each key -> row index\n            l = sorted(d[key], reverse = True)     # sort the list of streak lengths\n            ht = l[0]                              # initialize height with the max height\n            for i in range(len(l)):                # iterate over the list \n                ht = min(ht, l[i])                 # maximum height possible\n                width = i + 1                      # width = i + 1\n                area = max(area, ht*width)        # area = height x width\n        return area\n```\nEdit:\nAn alternate solution would be to calculate the number of ones till current cell. This avoids the iteration over the row indexes to assign streak length. \n```\nclass Solution:\n    def largestSubmatrix(self, matrix: List[List[int]]) -> int:\n        m,n = len(matrix), len(matrix[0])\n        res = 0\n        dp = [0]*n\n        \n        for i in range(m):\n            for j in range(n):\n                dp[j] = matrix[i][j]*(dp[j] + 1)\n        \n            cnt = 1\n            for x in sorted(dp, reverse = True):\n                res = max(x*cnt, res)\n                cnt += 1\n        \n        return res\n```
['Python', 'Python3']