We are given a `mxn` matrix filled with `0` / `1` and we need to return the area of largest square consisting of all `1`s\n\n---\n\n\u2714\uFE0F ***Solution - I (Brute-Force)***\n\nTo start with brute-force approach, we can simply consider each possible starting cell (`row`, `col`) and side length (`sideLen`) of square starting at that cell. For each cell and `sideLen`, we will check if the corresponding square inside the matrix is valid or not (i.e, all cells are `"1"` or not). After checking each possible squares, we will return the one with maximum area.\n\n```cpp\nclass Solution {\npublic:\n int maximalSquare(vector>& M) {\n auto isValidSquare = [&](int i, int j, int side) {\n return all_of(begin(M)+i, begin(M)+i+side, [&](auto& R){\n return all_of(begin(R)+j, begin(R)+j+side, [&](auto cell) { return cell == \'1\'; });\n });\n };\n int m = size(M), n = size(M[0]), ans = 0;\n for(int row = 0; row < m; row++)\n for(int col = 0; col < n; col++)\n for(int sideLen = 1; sideLen <= min(m-row, n-col); sideLen++) \n if(isValidSquare(row, col, sideLen))\n ans = ans = max(ans, sideLen*sideLen);\n return ans;\n }\n};\n```\n\nWe can slightly optimize the code by running from `sideLen = min(m, n)` down to `1` instead of the other way around. This ensures that we can return the area of sqaure as soon as we find the 1st valid square since that square would be the 1st valid square of maximum side length.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maximalSquare(vector>& M) {\n auto isValidSquare = [&](int i, int j, int side) {\n return all_of(begin(M)+i, begin(M)+i+side, [&](auto& R){\n return all_of(begin(R)+j, begin(R)+j+side, [&](auto cell) { return cell == \'1\'; });\n });\n };\n int m = size(M), n = size(M[0]);\n for(int sideLen = min(m, n); sideLen; sideLen--)\n for(int row = 0; row <= m-sideLen; row++)\n for(int col = 0; col <= n-sideLen; col++)\n if(isValidSquare(row, col, sideLen))\n return sideLen*sideLen;\n return 0;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n def is_valid_sqaure(row, col, side):\n return all(all(M[i][j] == \'1\' for j in range(col, col+side)) for i in range(row, row+side))\n m, n = len(M), len(M[0])\n for side_len in range(min(m,n), 0, -1):\n for row in range(m - side_len + 1):\n for col in range(n - side_len + 1):\n if is_valid_sqaure(row, col, side_len):\n return side_len**2\n return 0\n```\n\n***Time Complexity :*** O(M\\*N*min(M,N)³)\n***Space Complexity :*** `O(1)`, only constant extra space is being used\n\n---\n\n\u2714\uFE0F ***Solution - II (Optimized Brute-Force)***\n\nInstead of checking each possible side length for a square starting at a given cell, we can optimze the process by starting from `row` of that cell and expanding the side length for that row till it is possible. We will continue this for below rows as well, till consecutive ones found along rows (denoted by `allOnesRowLen`) > current row number. \n\nThe process is similar to the one shown in below diagram which I had used in my post for [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/discuss/1604254/C%2B%2B-Simple-Solution-w-Explanation-or-Optimizations-from-Brute-Force-to-DP) with only change that we stop further iteration as soon as `allOnesRowLen` exceeds current row number (because we need to form square in this case & max possible side length is already know by now).\n\n

\n Trulli \n

Taken From 85. Maximal Rectangle

\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int getMaxSquareLen(vector>& M, int row, int col) {\n int allOnesRowLen = min(size(M)-row, size(M[0])-col), sqLen = 0;\n for(int i = 0, j; i < allOnesRowLen; i++) {\n for(j = 0; j < allOnesRowLen && M[i+row][j+col] != \'0\'; j++);\n allOnesRowLen = j;\n sqLen = min(allOnesRowLen, i+1);\n }\n return sqLen;\n }\n int maximalSquare(vector>& M) {\n int m = size(M), n = size(M[0]), ans = 0;\n for(int row = 0; row < m; row++)\n for(int col = 0; col < n; col++) \n ans = max(ans, getMaxSquareLen(M, row, col));\n return ans * ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n m, n, ans = len(M), len(M[0]), 0\n def get_max_square_len(row, col):\n all_ones_row_len, sq_len, i, j = min(m-row, n-col), 0, 0, 0\n while i < all_ones_row_len:\n j = 0\n while j < all_ones_row_len and M[i+row][j+col] != \'0\': \n j += 1\n all_ones_row_len = j\n sq_len = min(all_ones_row_len, i := i + 1)\n return sq_len\n \n for row in range(m):\n for col in range(n):\n ans = max(ans, get_max_square_len(row, col))\n return ans * ans\n```\n\n\n***Time Complexity :*** O(MN*min(M,N)²)\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - III (Pre-processing / Dynamic Programming)***\n\nIn the previous approach, for computing the maximum square length that can be forme starting at `(row, col)` cell, we were iteratively calculating maximum consecutive ones in a given row (`allOnesRowLen`). This was done multiple times for each cell of the matrix. \n\nBut this can be optimized if we pre-compute the number of consecutive ones to the right for every cell. The following solution uses `ones` matrix where `ones[i][j]` denotes number of consecutive ones to the right of the `(i, j)` cell. \n\nNote that we could have also computed number of consecutive ones to the left or even number of consecutive ones to the top/bottom and modified the other code accordingly. It\'s just based on how you model the problem.\n\n```cpp\nclass Solution {\npublic:\n int getMaxSquareLen(vector>& M, vector>& ones, int row, int col) {\n int allOnesRowLen = min(size(M)-row, size(M[0])-col), sqLen = 0;\n for(int i = 0, j; i < allOnesRowLen; i++) \n allOnesRowLen = min(allOnesRowLen, ones[i+row][col]),\n sqLen = min(allOnesRowLen, i+1);\n return sqLen;\n }\n int maximalSquare(vector>& M) {\n int m = size(M), n = size(M[0]), ans = 0;\n vector> ones(m, vector(n+1));\n for(int i = m-1; ~i; i--)\n for(int j = n-1; ~j; j--)\n ones[i][j] = (M[i][j] == \'1\' ? 1 + ones[i][j+1] : 0);\n \n for(int row = 0; row < m; row++)\n for(int col = 0; col < n; col++) \n ans = max(ans, getMaxSquareLen(M, ones, row, col));\n return ans * ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n m, n, ans = len(M), len(M[0]), 0\n ones = [[0]*(n+1) for i in range(m)]\n for i in range(m-1,-1,-1):\n for j in range(n-1,-1,-1):\n ones[i][j] = 1 + ones[i][j+1] if M[i][j] == \'1\' else 0\n \n def get_max_square_len(row, col):\n all_ones_row_len, sq_len, i, j = min(m-row, n-col), 0, 0, 0\n while i < all_ones_row_len: \n all_ones_row_len = min(all_ones_row_len, ones[i+row][col])\n sq_len = min(all_ones_row_len, i := i + 1)\n return sq_len\n \n for row in range(m):\n for col in range(n):\n ans = max(ans, get_max_square_len(row, col))\n return ans * ans\n```\n\n***Time Complexity :*** O(MN*min(M,N))\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - IV (Dynamic Programming)***\n\nWe pre-processed the number of consecutive ones in the previous approach. For each cell, that allowed us to eliminate search over columns for consecutive ones, but we still had to iterate over the rows to find number of consecutive ones for each row & thus we found maximum square\'s side length starting at each cell.\n\nWe cannot simply precompute consecutive ones as well along each column. This may give us number of consecutive ones starting at `row` and `col` for a given cell, but we wouldnt be sure if every cell in the square thus formed will all be 1 as well.\n\n**So can we eliminate the need of search over rows?**\n\nEliminating this search would mean that we need to determine largest square starting at current cell by extending it from previous computations. As explained above, we cant only consider the consecutive ones along a row and column since we dont know if every other cell of square formed will also be `1`. This means that to know the max square length at a given cell `(row, col)`, we will also require to know if every cell in the subsquare (`row+1`, `col+1`) is also one. This directly means that we need to know the side length of square starting at cell `(row+1, col+1)`.\n\nSo, we can start from the last cells `(m, n)` of the given grid and iterate back till `(0, 0)` computing the side length of sqaure for each cell along the way. Since the length of side of square for current cell is determined by previous computations, this means we will be using **dynamic programming**.\n\nWe precompute `onesRow` and `onesCol` which give us the consecutive number of 1s starting at each cell (this is similar to `ones` computed previously). Then, we also use a `dp` matrix, where `dp[i][j]` denotes the maximum length of square starting at cell `(i, j)`. The current state can be computed using the state transition -\n1. `dp[i][j] = 0`, if `M[i][j] == \'0\'`, since no square can be formed if current cell itself is `\'0\'`\n2. `dp[i][j] = 1 + min(onesRow[i][j]-1, onesCol[i][j]-1, dp[i+1][j+1])`, if `M[i][j] == \'1\'`\n\nThe 2nd transition denotes that current cell is `\'1\'` so side length is atleast 1. On top of that, we will consider minimum amongst the number of consecutive ones along current row `i`, consecutive ones along current column `j` (`-1` in both case because we dont want to count current cell twice), and maximum valid square starting at `(i+1, j+1)`. This will give us the length of side of maximum square ensuring cells within it are all `\'1\'`.\n\nAfter we get side length of square at current cell, we can compute its area and finally return the maximum among all such areas found in the grid.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maximalSquare(vector>& M) {\n int m = size(M), n = size(M[0]), ans = 0;\n vector> dp(m+1, vector(n+1)), onesRow(dp), onesCol(dp);\n for(int i = m-1; ~i; i--)\n for(int j = n-1; ~j; j--)\n onesRow[i][j] = (M[i][j] == \'1\' ? 1 + onesRow[i][j+1] : 0),\n onesCol[i][j] = (M[i][j] == \'1\' ? 1 + onesCol[i+1][j] : 0);\n \n for(int i = m-1; ~i; i--)\n for(int j = n-1; ~j; j--) \n dp[i][j] = (M[i][j] == \'1\' ? 1 + min({onesRow[i][j]-1, onesCol[i][j]-1, dp[i+1][j+1]}) : 0),\n ans = max(ans, dp[i][j]);\n\n return ans * ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n m, n, ans = len(M), len(M[0]), 0\n dp, onesRow, onesCol = ([[0]*(n+1) for i in range(m+1)] for cnt in range(3))\n\n for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):\n onesRow[i][j] = 1 + onesRow[i][j+1] if M[i][j] == \'1\' else 0\n onesCol[i][j] = 1 + onesCol[i+1][j] if M[i][j] == \'1\' else 0\n \n for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):\n dp[i][j] = 1 + min(onesRow[i][j]-1, onesCol[i][j]-1, dp[i+1][j+1]) if M[i][j] == \'1\' else 0\n ans = max(ans, dp[i][j])\n return ans * ans\n\n```\n\nThe above solution can be futher optimized if we see that we don\'t really need to separately maintain `onesRow` and `onesCol`. We can get those values from `dp` as well, more specifically from `dp[i+1][j]` and `dp[i][j+1]`. \nRecall that we denoted `dp[i][j]` as maximum length of square starting at cell `(i, j)` which means they wont hold exact values of `onesRow` and `onesCol` (value maybe less in some cases) but it wont matter since we are taking minimum amongst the three anyway. (which means even if value in `onesRow / onesCol` was higher, we would have considered it if it wasnt forming a square).\n\nThus, the above solution is optimized as -\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maximalSquare(vector>& M) {\n int m = size(M), n = size(M[0]), ans = 0;\n vector> dp(m+1, vector(n+1));\n for(int i = m-1; ~i; i--)\n for(int j = n-1; ~j; j--) \n dp[i][j] = (M[i][j] == \'1\' ? 1 + min({dp[i+1][j], dp[i][j+1], dp[i+1][j+1]}) : 0),\n ans = max(ans, dp[i][j]);\n\n return ans * ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n m, n, ans = len(M), len(M[0]), 0\n dp = [[0]*(n+1) for i in range(m+1)]\n \n for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):\n dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) if M[i][j] == \'1\' else 0\n ans = max(ans, dp[i][j])\n return ans * ans\n```\n\n***Time Complexity :*** O(MN)\n***Space Complexity :*** `O(MN)`\n\n---\n\n\u2714\uFE0F ***Solution - V (Space-Optimized Dynamic Programming)***\n\nWe can see that we are only ever accessing the current row and next row of `dp`. Thus we dont need to store every row of it and can do away with only storing two rows. \n\nA common and easy way to convert 2D dp to linear space usage is by defining 2 rows in `dp` and alternating between those rows for each computation. This basically ensures we are using previous computed row to compute the current row and we dont even need to change the previous solution by much. We can simply alternate between rows using the mod 2(`%2`) or AND 1 (`& 1`) operations.\n\nThus, we can optmize on space as below -\n\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maximalSquare(vector>& M) {\n int m = size(M), n = size(M[0]), ans = 0;\n vector> dp(2, vector(n+1));\n for(int i = m-1; ~i; i--)\n for(int j = n-1; ~j; j--) \n dp[i&1][j] = (M[i][j] == \'1\' ? 1 + min({dp[(i+1)&1][j], dp[i&1][j+1], dp[(i+1)&1][j+1]}) : 0),\n ans = max(ans, dp[i&1][j]);\n\n return ans * ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n m, n, ans = len(M), len(M[0]), 0\n dp = [[0]*(n+1) for i in range(2)]\n \n for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):\n dp[i&1][j] = 1 + min(dp[(i+1)&1][j], dp[i&1][j+1], dp[(i+1)&1][j+1]) if M[i][j] == \'1\' else 0\n ans = max(ans, dp[i&1][j])\n return ans * ans\n\n```\n\n\n***Time Complexity :*** O(MN)\n***Space Complexity :*** `O(N)`, this can be further optimized to `O(min(M, N))` as well.\n\n\n---\n\n\u2714\uFE0F ***Solution - VI (Space-Optimized Dynamic Programming - Inline using input Matrix)***\n\nWe can further optimize the code if we use the input matrix itself as a `dp` matrix. This is possible if input is allowed to be modified (or you can use the same code by simply making a copy of input matrix). \n\nThis type of solution will most likely fail in some languages (such as C++/Java) on addition on newer test cases due to char overflow, but it can work in language like python.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n int maximalSquare(vector>& M) {\n int m = size(M), n = size(M[0]), ans = 0; \n for(int i = m-1; ~i; i--)\n for(int j = n-1; ~j; j--) \n if(i == m-1 or j == n-1)\n ans = max(ans, int(M[i][j] -= \'0\'));\n else\n M[i][j] = (M[i][j] == \'1\' ? 1+min({M[i+1][j], M[i][j+1], M[i+1][j+1]}) : 0),\n ans = max(ans, int(M[i][j]));\n\n return ans * ans;\n }\n};\n```\n\n**Python**\n```python\nclass Solution:\n def maximalSquare(self, M):\n m, n, ans = len(M), len(M[0]), 0\n for i, j in product(range(m-1, -1, -1), range(n-1, -1, -1)):\n if i == m-1 or j == n-1:\n M[i][j] = int(M[i][j])\n ans = max(ans, M[i][j])\n else:\n M[i][j] = 1 + min(M[i+1][j], M[i][j+1], M[i+1][j+1]) if M[i][j] == \'1\' else 0\n ans = max(ans, M[i][j])\n return ans * ans\n```\n\n***Time Complexity :*** O(MN)\n***Space Complexity :*** `O(1)`\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---

Maximal Square

Problem Description

Problem Description

Answer Panel