Maximal Square


  • 0

    Click here to see the full article post


  • 0

    Nice job guys


  • 0

    Thank you very much for your detailed explanation.


  • 1

    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.


  • 1

    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 0

    the single bold 1 is a maximal square-containing-only-ones. Because you can't add to it to get a larger square-containing-only-ones. It's not a part of any larger square-containing-only-ones. It's not a maximum square-containing-only-ones, 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 :-)).


  • 0

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


  • 0

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


  • 0
    F

    Beautiful solution. Thank you very much.


  • 0
    K

    On line 4 in approach #2,

    int[][] dp = new int[rows + 1][cols + 1];
    

    Could anyone please explain why dp is initialized with one bigger than the original matrix rows and cols? In the diagram, the original matrix and dp matrix are same size.


  • 1
    D

    @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;
    }
    

    }


  • 0
    E

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


  • 0
    A

    How can one come up with this solution during an interview........


  • 0
    T

    @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.


  • 0
    S

    nice explanation, nice node.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.