Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Maximal Square

Maximal Square

Master this topic with zero to advance depth.

Maximal Square

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Visual Representation

Matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 The 2x2 square of 1s at (1,2) to (2,3) is one of the squares. Wait, there is a larger one? No, area is 4. DP Strategy: dp[i][j] = side length of the largest square ending at (i, j).
Medium

Examples

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Approach 1

Level I: Dynamic Programming (2D)

Intuition

A square of size k ending at (i, j) can only be formed if there are squares of size k-1 ending at (i-1, j), (i, j-1), and (i-1, j-1).

Thought Process

  1. dp[i][j] represents the side length of the largest square ending at matrix[i][j].
  2. If matrix[i][j] == '1':
    • dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
  3. Keep track of the maximum side length found so far.
  4. Result = maxSide * maxSide.
⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

Matrix: 1 1 1 1

i\j01
011
11min(1, 1, 1)+1 = 2
Result: 2^2 = 4
java
public class Main {
    public static int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSide = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1'}, {'1','1','1'}, {'1','1','1'}};
        System.out.println(maximalSquare(matrix)); // 4
    }
}
Approach 2

Level II: Memoization (Top-Down)

Intuition

Cache the result of dp(i, j) so each cell is computed only once. The recurrence: dp(i,j) = min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1)) + 1 if matrix[i][j]=='1'.

Visual

Matrix: Memo: 1 1 1 1 1 1 1 1 1 -> 1 2 ? 1 1 1 1 ? 3 <- dp(2,2) = min(2,2,2)+1=3
⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

dp(2,2): matrix[2][2]='1'. min(dp(1,2)=2, dp(2,1)=2, dp(1,1)=2)+1=3. Area=9.

java
import java.util.Arrays;

public class Main {
    static int[][] memo;
    static char[][] mat;
    static int solve(int i, int j) {
        if (i < 0 || j < 0 || mat[i][j] == '0') return 0;
        if (memo[i][j] != -1) return memo[i][j];
        return memo[i][j] = 1 + Math.min(solve(i-1,j), Math.min(solve(i,j-1), solve(i-1,j-1)));
    }

    public static int maximalSquare(char[][] matrix) {
        mat = matrix; int m = matrix.length, n = matrix[0].length;
        memo = new int[m][n];
        for (int[] r : memo) Arrays.fill(r, -1);
        int maxS = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) maxS = Math.max(maxS, solve(i,j));
        return maxS * maxS;
    }

    public static void main(String[] args) {
        char[][] m = {{"1","1"},{"1","1"}};
        System.out.println(maximalSquare(m)); // 4
    }
}
Approach 3

Level III: Space Optimized (1D)

Intuition

We only need the previous row and the current row. Specifically, dp[i-1][j], dp[i][j-1], and the diagonal dp[i-1][j-1].

Logic Steps

  1. Initialize a dp array of size n + 1.
  2. Use a prev variable to store the diagonal value dp[i-1][j-1] from the previous row.
  3. Iterate row by row.
⏱ O(M * N)💾 O(N)

Detailed Dry Run

Same logic as 2D but overwriting the same row array. 'prev' variable caches the upper-left (diagonal) value before it gets updated for the current row's calculation.

java
public class Main {
    public static int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int maxSide = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], dp[j]), prev) + 1;
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        char[][] matrix = {{'1','1'}, {'1','1'}};
        System.out.println(maximalSquare(matrix)); // 4
    }
}
← Previous QuestionMinimum Path Sum in Grid
Next Question →Palindrome Partitioning II