Largest square formed in a matrix

Time: O(n*m)

Space: O(n*m)

Intuition

DP: dp[i][j] = side length of largest square with bottom-right corner at (i,j). Recurrence: min(left, top, top-left)+1 if cell is 1.

Algorithm

1dp[i][j] = 0 if mat[i][j]==0.
2dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if mat[i][j]==1.
3Answer = max(dp[i][j]).

Common Pitfalls

•Same as Maximal Square (LC 221). Answer is max side length, not area.

Largest square formed in a matrix.java

Java

// Approach: DP. dp[i][j] = side of largest square with bottom-right at (i,j) = 1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
// Time: O(n*m) Space: O(n*m)
class Solution {
    static int maxSquare(int n, int m, int mat[][]) {
        int[][] dp = new int[n][m];

        int maxSize = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1) {
                    if (i == 0 || j == 0)
                        dp[i][j] = 1;
                    else {
                        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                Math.min(dp[i - 1][j], dp[i][j - 1]));
                    }

                    maxSize = Math.max(maxSize, dp[i][j]);
                }
            }
        }

        return maxSize;
    }
}

Was this solution helpful?