DP solution faster than 99.8% w/ description, example & analysis - O(nm + n³) time / O(1) space
Solution:\n\n/* Leetcode speedup */\nstatic vector<vector<char>> mat {[](){\n    std::ios::sync_with_stdio(false);\n    std::cin.tie(NULL);\n    std::cout.tie(N
# Solution:\n```\n/* Leetcode speedup */\nstatic vector<vector<char>> mat {[](){\n    std::ios::sync_with_stdio(false);\n    std::cin.tie(NULL);\n    std::cout.tie(NULL);\n    return NULL;\n}()};\n\n/* Solution */\nclass Solution {\npublic:\n    int maximalRectangle(vector<vector<char>> &mat) {\n\t\t// Iterate over mat and count the number of contiguous 1\'s to the left of each position\n        for (int i {0}; i < mat.size(); ++i) {\n            for (int j {1}; j < mat.front().size(); ++j) {\n                mat[i][j] = mat[i][j] != \'0\' ? mat[i][j-1] + 1 : mat[i][j];\n            }\n        }\n\n\t\t// Return value -- area of maximal 1\'s rectangle \n        int ret {0};\n\t\t\n\t\t// Iterate over new values and calculate/find area of maximal 1\'s rectangle\n        for (int i {0}; i < mat.size(); ++i) { \n            for (int j {0}; j < mat.front().size(); ++j) {\n                for (int k {i}, minw {mat[i][j] - \'0\'}; k < mat.size() && minw; ++k) {\n                    ret = max(ret, (k - i + 1) * (minw= min(minw, mat[k][j] - \'0\')));\n\t\t\t\t\tmat[k][j] = mat[k][j] - \'0\' <= minw ? \'0\' : mat[k][j];\n                }\n            }\n        }\n    \n\t\t// Return area of maximal rectangle\n        return ret;\n    }\n};\n```\n\n\n# Description:\nFirst, the algorithm iterates over the elements in the matrix and counts the number of horizontally contiguous 1\u2019s to the left of each position. Starting at the 2nd element (1th position) of each row, if the current element, ```mat[i][j]```, is ```\u20181\u2019```, then its value is set to that of the previous element in the same row plus one.\n\ni.e., if ```mat[i][j] == \u20181\u2019``` then  ```mat[i][j] = mat[i][j-1] + 1```, else ```mat[i][j]``` remains ```\'0\'```. \n\nHere there\'s one iteration for each element, and the original matrix is modified to count horizontally contiguous 1\u2019s. Hence, the time complexity for this portion is O(nm), and the space complexity is O(1).\n \n*Note: since the matrix holds char types and not ints, it\u2019s necessary to subtract  \u20180\u2019 from elements to obtain an accurate numerical value for the number of horizontally contiguous 1\u2019s counted. Alternatively, you could use an identical 2d vector of ints for counting, but this would change the space complexity from O(1) to O(nm).*\n \nTake the following example matrix: \n\n ```\nvector<vector<char>> mat {\n    { \'0\', \'1\', \'1\', \'1\', \'0\' },\n    { \'0\', \'1\', \'1\', \'0\', \'0\' }, \n    { \'0\', \'0\', \'0\', \'0\', \'1\' },\n    { \'1\', \'1\', \'0\', \'0\', \'0\' } \n};\n```\n\nAfter iterating over the elements and counting the number of horizontally contiguous 1\u2019s for each position, the values (after having subtracted \u20180\u2019 from them) for each element would be:\n \n ```\n0 1 2 3 0 \n0 1 2 0 0 \n0 0 0 0 1 \n1 2 0 0 0 \n ```\n \nNext, the new values are iterated over and used to calculate areas of rectangles in the matrix originally, and the maximal area calculated is kept track of with the return variable ```ret```.\n \nThis is done using three nested loops:\n1. The outermost loop iterates vertically over the rows of the matrix, from ```i = 0``` to ```i = n-1```. \n2. The second loop iterates horizontally over the columns, from ```j = 0``` to ```j = m-1```. \n3. The innermost loop also iterates over the rows, from```k = i``` to ```k = n-1```, but only while the value of ```mat[k][j]``` is not ```\'0\'``` (i.e., non-zero).\n \nAs we iterate vertically over elements in the innermost loop, we keep track of the minimum (non-zero) value encountered for ```mat[k][j]```. This value represents the largest width for which the elements iterated over by ```k``` form a rectangle without any gaps or holes. Moreover, since these elements make up one side of the rectangle, the number of elements iterated over consecutively in this loop, ```k - i + 1```, represents the height of the rectangle they form.\n\nUsing these values for width and height, each iteration we calculate the area of the largest possible rectangle and keep track of the overall maximal area found. \n\nAdditionally, an optimization is made by setting ```mat[k][j] = \'0\'``` when its numerical value (```mat[k][j] - \'0\'```) is not greater than ```minw```. This allows duplicate iterations over elements we know will not produce a larger area to be avoided. \n \n#  Example:\n\nGiven the following example input matrix:\n \n ```\nvector<vector<char>> mat {\n    { \'0\', \'1\', \'1\', \'1\', \'0\' },\n    { \'0\', \'1\', \'1\', \'0\', \'0\' }, \n    { \'0\', \'0\', \'0\', \'0\', \'1\' },\n    { \'1\', \'1\', \'0\', \'0\', \'0\' } \n};\n```\n\n\nAfter iterating over the matrix the first time and recording the number of contiguous 1\'s to the left of each position the values become:\n\n![image](https://assets.leetcode.com/users/dd0rz/image_1547590069.png)\n\n\n*Note: integer values shown for mat, i.e., mat[][] - \'0\'*\n\nNext, the new values are iterated over and used to calculate the area of 1\'s rectangles in the matrix originally. The first several iterations where area calculations are performed are as follows (note that the innermost loop does not execute and no calculations are performed when ```mat[i][j] == \'0\'```, thus these iterations are not shown):\n\n![image](https://assets.leetcode.com/users/dd0rz/image_1547588408.png)\n\nAfter completion, the maximal rectangle returned for the given matrix is ```ret = 4```.\n\n# Computational Complexity\n**Worst-case Space Complexity**\nSince our solution modifies the original input matrix and uses a constant amount of memory rather than some amount based on the input size, our space complexity is constant time, O(1). \n\n**Worst-case Time Complexity**\nTo analyze the worst-case runtime complexity, consider a 5x5 matrix with the worst-case configuration:\n\n```\n0, 0, 0, 0, 1\n0, 0, 0, 1, 1\n0, 0, 1, 1, 1\n0, 1, 1, 1, 1\n1, 1, 1, 1, 1\n```\n\nWhen counting horizontally contiguous 1\'s in the first set of loops, there\'s one iteration for each element in the matrix. Hence the runtime complexity for this part is O(nm), where where n = height and w = width. Next, we consider the now modified worst-case 5x5 matrix to determine the runtime complexity of the second set of loops:\n\n```\n0, 0, 0, 0, 1\n0, 0, 0, 1, 2\n0, 0, 1, 2, 3\n0, 1, 2, 3, 4\n1, 2, 3, 4, 5\n```\n\nIt\'s now apparent this is the worst-case configuration because when calculating areas smaller widths are always checked before larger ones. This prevents duplicate iterations from being avoided by setting elements to 0. \n\nSince the two outer loops in the second part will produce one iteration for each element in the matrix, we\'ll always have nm iterations plus any additional duplicate iterations over elements performed by the innermost loop. If we can find an expression, X, for the number of extra iterations over elements performed by the innermost loop, then we\'ll know the runtime complexity for this part is O(nm + X).\n\nStart by considering elements in the rightmost column, ```j=4```. When ```i=0``` and the innermost loop is entered, all elements in the column from [```k=0``` to ```k=4```] will be iterated over for 5 iterations total. This is the first time iterating over any element in the column, so none of the iterations are extra iterations. When ```i=1``` elements in the column from [```k=1``` to ```k=4```] (from the value 2 downwards) will be iterated over for 4 iterations total. This time these will all be duplicate iterations since all elements in the column have been iterated over already. When ```i=2```, elements in the column from [```k=2``` to ```k=4```] are iterated over for 3 iterations total, which again are all duplicate iterations. For all values of ```i``` the number of duplicate iterations over elements in rightmost column, ```j=4```, will be:\n\n*4 + 3 + 2 + 1 = 10*\n\nFor the preceding column, ```j=3```, the first element is 0, so there are no iterations over elements in the column when ```i=0```. Starting at ```i=1```, however, we can see the same pattern as before will occur. This means the total number of duplicate iterations over elements in the column for all values of ```i``` will be:\n\n*3 + 2 + 1 = 6*\n\nThe same pattern occurs for all columns in the matrix, and the number of duplicate iterations over elements in each will be:\n\n*1st column (```j=0```): 0 = 0\n2nd column (```j=1```): 1 + 0 = 1\n3rd column (```j=2```): 2 + 1 + 0 = 3\n4th column (```j=3```): 3 + 2 + 1 + 0 = 6\n5th column (```j=4```): 4 + 3 + 2 + 1 + 0 = 10*\n\nIt can be seen for the worst-case configuration, in each column the number of duplicate iterations over elements will be the sum of the first n-1 natural numbers, where n is the largest value in the column. Putting n-1 into the equation n(n+1)/2 (sum of natural numbers up to n), for each column we have:\n\n*(n-1)(n-1+1)/2 = n(n-1)/2 duplicate iterations*\n\nThus, for all columns in the matrix, the total number duplicate iterations is:\n\n*\u03A3n(n-1)/2 [1 => n]*, or equivalently, *n\xB3/6 - n/6*\n\nThis means for our worst-case 5x5 matrix we should have nm iterations + n\xB3/6 - n/6 duplicate iterations:\n\n*5 * 5 + 125/6 - 5/6 = 25 iterations + 20 duplicate iterations = 45 total iterations*, which is accurate.\n\nCombining both the first and second parts, our overall worst-case time is:\n\n*O(nm) + O(nm + n\xB3/6 - n/6) = O(2nm + n\xB3/6 - n/6) =*\n\n*O(nm + n\xB3)*, where n = height and m = width.
[]