Maximal Square


Could the question and article finally be fixed, though? It says:
find the largest square containing all 1's and return its area.
It should say "containing only 1's". Same as in the Maximal Rectangle problem which asks for the "largest rectangle containing all ones" instead of the "largest rectangle containing only ones". Has been pointed out and upvoted quite a bit already.

Btw, something about the title, more precisely the word "maximal": In math/compsci, that roughly speaking means something that can't be made larger by adding something to it. For example, in the matrix
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0the single bold 1 is a maximal squarecontainingonlyones. Because you can't add to it to get a larger squarecontainingonlyones. It's not a part of any larger squarecontainingonlyones. It's not a maximum squarecontainingonlyones, though, because there are larger ones. So the title of the problem should say maximum, not maximal. (No, I don't expect this to be changed, just wanted to point it out, maybe for the future or just for education :)).

@StefanPochmann lol my advisor always points out the same thing when somebody says maximal instead of maximum inappropriately!

@StefanPochmann Thanks for pointing that out. I have fixed both problems' description.

@keitaito You are right. The picture and depiction in article isn't consistent with its code.
I think code should be like below to follow the first image. It created a col * row size dp matrix, but added judgement for i != 0 && j != 0.
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
int[][] dp = new int[rows][cols];
int maxsqlen = 0;for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (i == 0  j == 0) { dp[i][j] = matrix[i][j] == '1' ? 1 : 0; maxsqlen = Math.max(maxsqlen, dp[i][j]); } else if (matrix[i][j] == '1') { dp[i][j] = Math.min(Math.min(dp[i][j  1], dp[i  1][j]), dp[i  1][j  1]) + 1; maxsqlen = Math.max(maxsqlen, dp[i][j]); } } } return maxsqlen * maxsqlen; }
}

guess i love histogram too much...
https://leetcode.com/submissions/detail/134840188/

@keitaito
when iterating the first row or first column, the formula for dp(i, j) is checking for values out of bounds. By shifting the whole dp to the right and bottom by 1 and adding a padding of 0's to the 1st row and 1st column, it makes the formula work without checking for boundaries.