Maximum Size Square Sub-Matrix with All 1s

Given a binary matrix mat[][] of size n × m, find out the maximum length of a side of a square sub-matrix with all 1s.

Example:

Input:
mat[][] = [
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0] ]
Output: 3
Explanation: The maximum length of a side of the square sub-matrix is 3 where every element is 1.

Input:
mat[][] = [[1, 1],
[1, 1]]

Output: 2
Explanation: The maximum length of a side of the square sub-matrix is 2. The matrix itself is the maximum sized sub-matrix in this case.

Try it on GfG Practice

Table of Content

[Naive Approach] - Using Recursion - O(3^(n+m)) Time and O(n+m) Space
[Better Approach - 1] - Using Top-Down DP (Memoization) - O(n × m) Time and O(n × m) Space
[Better Approach - 2] -Using Bottom-Up DP (Tabulation) – O(n × m) Time and O(n × m) Space
[Expected Approach] - Using Space Optimized DP – O(n × m) Time and O(n) Space

[Naive Approach] - Using Recursion - O(3^(n+m)) Time and O(n+m) Space

The idea is to recursively determine the side length of the largest square sub-matrix with all 1s at each cell. For each cell, if its value is 0, we return 0 since it cannot contribute to a square. Otherwise, we calculate the possible side length of a square ending at this cell by finding the minimum square side lengths from the right, bottom, and bottom-right diagonal cells and adding 1 to this minimum. This value gives the largest possible square side length for that cell, and we update the maximum side length by comparing it with the result at each cell.

The recurrence equation will be as follows:

Side(i, j) = 1 + minimum(Side(i, j+1), Side(i+1, j), Side(i+1, j+1)) for cells i, j where mat[i][j] = 1.
Otherwise Side(i,j) = 0.

C++

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

//recursive function to find the square
int maxSquareRecur(int i, int j, vector<vector<int>> &mat, int &ans) {
    
    // Return 0 for invalid cells
    if (i<0 || i==mat.size() || j<0 || j==mat[0].size()) 
        return 0;
    
     // for the side square
    int right = maxSquareRecur(i, j+1, mat, ans);
    int down = maxSquareRecur(i+1, j, mat, ans);
    int diagonal = maxSquareRecur(i+1, j+1, mat, ans);
    
    // If mat[i][j]==0, then square cannot
    // be formed.
    if (mat[i][j]==0) return 0;
    
    // Side of square will be 
    int val = 1+ min({right, down, diagonal});
    ans = max(ans, val);
    
    return val;
}

// for calculate the answer
int maxSquare(vector<vector<int>> &mat) {

    int ans = 0;
    maxSquareRecur(0,0,mat, ans);
    return ans;
}

int main() {
    vector<vector<int>> mat = 
    {{0, 1, 1, 0, 1}, 
     {1, 1, 0, 1, 0},
     {0, 1, 1, 1, 0},
     {1, 1, 1, 1, 0},
     {1, 1, 1, 1, 1},
     {0, 0, 0, 0, 0}};
    cout << maxSquare(mat) << endl;

    return 0;
}

Java

public class GfG {

    // recursive function to find the square
    static int maxSquareRecur(int i, int j, int[][] mat, int[] ans) {

        // Return 0 for invalid cells
        if (i < 0 || i == mat.length || j < 0 || j == mat[0].length)
            return 0;

        // for the side square
        int right = maxSquareRecur(i, j + 1, mat, ans);
        int down = maxSquareRecur(i + 1, j, mat, ans);
        int diagonal = maxSquareRecur(i + 1, j + 1, mat, ans);

        // If mat[i][j]==0, then square cannot be formed.
        if (mat[i][j] == 0) return 0;

        // Side of square will be
        int val = 1 + Math.min(right, Math.min(down, diagonal));
        ans[0] = Math.max(ans[0], val);

        return val;
    }

    // for calculate the answer
    static int maxSquare(int[][] mat) {
        int[] ans = new int[1];
        maxSquareRecur(0, 0, mat, ans);
        return ans[0];
    }

    public static void main(String[] args) {
        int[][] mat = {
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

        System.out.println(maxSquare(mat));
    }
}

Python

# recursive function to find the square
def maxSquareRecur(i, j, mat, ans):

    # Return 0 for invalid cells
    if i < 0 or i == len(mat) or j < 0 or j == len(mat[0]):
        return 0

    # for the side square
    right = maxSquareRecur(i, j + 1, mat, ans)
    down = maxSquareRecur(i + 1, j, mat, ans)
    diagonal = maxSquareRecur(i + 1, j + 1, mat, ans)

    # If mat[i][j]==0, then square cannot be formed.
    if mat[i][j] == 0:
        return 0

    # Side of square will be
    val = 1 + min(right, down, diagonal)
    ans[0] = max(ans[0], val)

    return val


# for calculate the answer
def maxSquare(mat):
    ans = [0]
    maxSquareRecur(0, 0, mat, ans)
    return ans[0]

if __name__=="__main__":
    mat = [
        [0,1,1,0,1],
        [1,1,0,1,0],
        [0,1,1,1,0],
        [1,1,1,1,0],
        [1,1,1,1,1],
        [0,0,0,0,0]
    ]
    
    print(maxSquare(mat))

using System;

class GfG
{
    // recursive function to find the square
    static int MaxSquareRecur(int i, int j, int[,] mat, ref int ans)
    {
        int rows = mat.GetLength(0);
        int cols = mat.GetLength(1);

        // Return 0 for invalid cells
        if (i < 0 || i == rows || j < 0 || j == cols)
            return 0;

        // for the side square
        int right = MaxSquareRecur(i, j + 1, mat, ref ans);
        int down = MaxSquareRecur(i + 1, j, mat, ref ans);
        int diagonal = MaxSquareRecur(i + 1, j + 1, mat, ref ans);

        // If mat[i][j]==0, then square cannot be formed.
        if (mat[i, j] == 0) return 0;

        // Side of square will be
        int val = 1 + Math.Min(right, Math.Min(down, diagonal));
        ans = Math.Max(ans, val);

        return val;
    }

    // for calculate the answer
    static int MaxSquare(int[,] mat)
    {
        int ans = 0;
        MaxSquareRecur(0, 0, mat, ref ans);
        return ans;
    }

    static void Main()
    {
        int[,] mat = {
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

        Console.WriteLine(MaxSquare(mat));
    }
}

JavaScript

// recursive function to find the square
function maxSquareRecur(i, j, mat, ans) {

    // Return 0 for invalid cells
    if (i < 0 || i == mat.length || j < 0 || j == mat[0].length)
        return 0;

    // for the side square
    let right = maxSquareRecur(i, j + 1, mat, ans);
    let down = maxSquareRecur(i + 1, j, mat, ans);
    let diagonal = maxSquareRecur(i + 1, j + 1, mat, ans);

    // If mat[i][j]==0, then square cannot be formed.
    if (mat[i][j] === 0) return 0;

    // Side of square will be
    let val = 1 + Math.min(right, down, diagonal);
    ans.value = Math.max(ans.value, val);

    return val;
}

// for calculate the answer
function maxSquare(mat) {
    let ans = { value: 0 };
    maxSquareRecur(0, 0, mat, ans);
    return ans.value;
}


// Driver code
let mat = [
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
];

console.log(maxSquare(mat));

Output

[Better Approach - 1] - Using Top-Down DP ( Memoization) - O(n × m) Time and O(n × m) Space

The recursive calls use sub-problems so if we get a sub-problem the first time, we can solve this problem by creating a 2-D array that can store a particular state. Now if we come across the same state again instead of calculating it again we can directly return its result stored in the table in constant time.

The recursive solution holds the following two properties of Dynamic Programming:

1. Optimal Substructure:

The side of square originating from i, j, i.e., maxSquare(i, j), depends on the optimal solutions of the sub-problems maxSquare(i, j+1) , maxSquare(i+1, j) and maxSquare(i+1, j+1). By finding the minimum value in these optimal substructures, we can efficiently calculate the side of square at (i,j).

2. Overlapping Sub-problems:

While applying a recursive approach in this problem, we notice that certain sub-problems are computed multiple times.

There are two parameters, i and j that changes in the recursive solution. So we create a 2D array of size n × m for memoization.
We initialize this array as -1 to indicate nothing is computed initially.
Now we modify our recursive solution to first check if the value is -1, then only make recursive calls. This way, we avoid re-computations of the same sub-problems.

C++

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

// recursive function to find the square
int maxSquareRecur(int i, int j, vector<vector<int>> &mat, 
                   int &ans, vector<vector<int>> &memo) {
    
    // Return 0 for invalid cells
    if (i<0 || i==mat.size() || j<0 || j==mat[0].size()) 
        return 0;
        
    // If value is memoized, return value.
    if (memo[i][j]!=-1) return memo[i][j];
    
   // for the side square
    int right = maxSquareRecur(i, j+1, mat, ans, memo);
    int down = maxSquareRecur(i+1, j, mat, ans, memo);
    int diagonal = maxSquareRecur(i+1, j+1, mat, ans, memo);
    
    // If mat[i][j]==0, then square cannot
    // be formed.
    if (mat[i][j]==0) return memo[i][j] = 0;
    
    // Side of square will be 
    int val = 1+min({right, down, diagonal});
    ans = max(ans, val);
    
    // Memoize the value and return it.
    return memo[i][j] = val;
}

int maxSquare(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();
    int ans = 0;
    
    // Create 2d array for memoization
    vector<vector<int>> memo(n, vector<int>(m, -1));
    maxSquareRecur(0,0,mat, ans,memo);
    return ans;
}

int main() {
    vector<vector<int>> mat = 
    {{0, 1, 1, 0, 1}, 
     {1, 1, 0, 1, 0},
     {0, 1, 1, 1, 0},
     {1, 1, 1, 1, 0},
     {1, 1, 1, 1, 1},
     {0, 0, 0, 0, 0}};
    cout << maxSquare(mat) << endl;

    return 0;
}

Java

import java.util.Arrays;

class GfG {

    // recursive function to find the square
    static int maxSquareRecur(int i, int j, int[][] mat,
                              int[] ans, int[][] memo) {

        // Return 0 for invalid cells
        if (i < 0 || i == mat.length || j < 0
            || j == mat[0].length)
            return 0;

        // If value is memoized, return value.
        if (memo[i][j] != -1)
            return memo[i][j];

        // for the side square
        int right
            = maxSquareRecur(i, j + 1, mat, ans, memo);
        int down = maxSquareRecur(i + 1, j, mat, ans, memo);
        int diagonal
            = maxSquareRecur(i + 1, j + 1, mat, ans, memo);

        // If mat[i][j]==0, then square cannot
        // be formed.
        if (mat[i][j] == 0)
            return memo[i][j] = 0;

        // Side of square will be
        int val
            = 1 + Math.min(right, Math.min(down, diagonal));
        ans[0] = Math.max(ans[0], val);

        // Memoize the value and return it.
        return memo[i][j] = val;
    }

    static int maxSquare(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[] ans = { 0 };

        // Create 2d array for memoization
        int[][] memo = new int[n][m];
        for (int[] row : memo)
            Arrays.fill(row, -1);

        maxSquareRecur(0, 0, mat, ans, memo);
        return ans[0];
    }

    public static void main(String[] args) {
        int[][] mat
            = { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
                { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 },
                { 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0 } };
        System.out.println(maxSquare(mat));
    }
}

Python

#  recursive function to find the square
def maxSquareRecur(i, j, mat, ans, memo):

    # Return 0 for invalid cells
    if i < 0 or i == len(mat) or j < 0 or j == len(mat[0]):
        return 0

    # If value is memoized, return value.
    if memo[i][j] != -1:
        return memo[i][j]

    # for the side square
    right = maxSquareRecur(i, j + 1, mat, ans, memo)
    down = maxSquareRecur(i + 1, j, mat, ans, memo)
    diagonal = maxSquareRecur(i + 1, j + 1, mat, ans, memo)

    # If mat[i][j]==0, then square cannot
    # be formed.
    if mat[i][j] == 0:
        memo[i][j] = 0
        return 0

    # Side of square will be
    val = 1 + min(right, down, diagonal)
    ans[0] = max(ans[0], val)

    # Memoize the value and return it.
    memo[i][j] = val
    return val


def maxSquare(mat):
    n, m = len(mat), len(mat[0])
    ans = [0]

    # Create 2d array for memoization
    memo = [[-1 for _ in range(m)] for _ in range(n)]
    maxSquareRecur(0, 0, mat, ans, memo)
    return ans[0]


if __name__ == "__main__":
    mat = [
        [0, 1, 1, 0, 1],
        [1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0],
        [1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1],
        [0, 0, 0, 0, 0]
    ]
    print(maxSquare(mat))

using System;

class GfG {
    
    // recursive function to find the square
    static int maxSquareRecur(int i, int j, int[, ] mat,
                              int[] ans, int[, ] memo) {

        // Return 0 for invalid cells
        if (i < 0 || i == mat.GetLength(0) || j < 0
            || j == mat.GetLength(1))
            return 0;

        // If value is memoized, return value.
        if (memo[i, j] != -1)
            return memo[i, j];

        // for the side square
        int right
            = maxSquareRecur(i, j + 1, mat, ans, memo);
        int down = maxSquareRecur(i + 1, j, mat, ans, memo);
        int diagonal
            = maxSquareRecur(i + 1, j + 1, mat, ans, memo);

        // If mat[i][j]==0, then square cannot
        // be formed.
        if (mat[i, j] == 0)
            return memo[i, j] = 0;

        // Side of square will be
        int val
            = 1 + Math.Min(right, Math.Min(down, diagonal));
        ans[0] = Math.Max(ans[0], val);

        // Memoize the value and return it.
        return memo[i, j] = val;
    }

    static int maxSquare(int[, ] mat) {
      
        int n = mat.GetLength(0), m = mat.GetLength(1);
        int[] ans = { 0 };

        // Create 2d array for memoization
        int[, ] memo = new int[n, m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                memo[i, j] = -1;

        maxSquareRecur(0, 0, mat, ans, memo);
        return ans[0];
    }

    static void Main() {
      
        int[, ] mat
            = { { 0, 1, 1, 0, 1 }, { 1, 1, 0, 1, 0 },
                { 0, 1, 1, 1, 0 }, { 1, 1, 1, 1, 0 },
                { 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0 } };
        Console.WriteLine(maxSquare(mat));
    }
}

JavaScript

// recursive function to find the square
function maxSquareRecur(i, j, mat, ans, memo) {

    // Return 0 for invalid cells
    if (i < 0 || i === mat.length || j < 0
        || j === mat[0].length)
        return 0;

    // If value is memoized, return value.
    if (memo[i][j] !== -1)
        return memo[i][j];
    
    // for the side square
    let right = maxSquareRecur(i, j + 1, mat, ans, memo);
    let down = maxSquareRecur(i + 1, j, mat, ans, memo);
    let diagonal
        = maxSquareRecur(i + 1, j + 1, mat, ans, memo);

    // If mat[i][j]==0, then square cannot
    // be formed.
    if (mat[i][j] === 0)
        return memo[i][j] = 0;

    // Side of square will be
    let val = 1 + Math.min(right, down, diagonal);
    ans[0] = Math.max(ans[0], val);

    // Memoize the value and return it.
    memo[i][j] = val;
    return val;
}

function maxSquare(mat) {
    let n = mat.length, m = mat[0].length;
    let ans = [ 0 ];

    // Create 2d array for memoization
    let memo
        = Array.from({length : n}, () => Array(m).fill(-1));
    maxSquareRecur(0, 0, mat, ans, memo);
    return ans[0];
}

let mat = [
    [ 0, 1, 1, 0, 1 ], [ 1, 1, 0, 1, 0 ], [ 0, 1, 1, 1, 0 ],
    [ 1, 1, 1, 1, 0 ], [ 1, 1, 1, 1, 1 ], [ 0, 0, 0, 0, 0 ]
];
console.log(maxSquare(mat));

Output

[Better Approach - 2] -Using Bottom-Up DP (Tabulation) – O(n × m) Time and O(n × m) Space

The approach is similar to the previous one, just instead of breaking down the problem recursively, we iteratively build up the solution by calculating in bottom-up manner. The idea is to create a 2-D array. Then fill the values using dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) for cells having value equal to 1. Otherwise, set dp[i][j] = 0.

C++

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int maxSquare(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();
    int ans = 0;
    
    // Create 2d array for tabulation
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    
    // Fill the dp 
    for (int i=n-1; i>=0; i--) {
        for (int j=m-1; j>=0; j--) {
            
            // If square cannot be formed
            if (mat[i][j] == 0) {
                dp[i][j] = 0;
                continue;
            }
            
            // check all 3 sides
            dp[i][j] = 1 + min({dp[i][j+1], 
            dp[i+1][j], dp[i+1][j+1]});
            
            ans = max(ans, dp[i][j]);
        }
    }
    
    return ans;
}

int main() {
    vector<vector<int>> mat = 
    {{0, 1, 1, 0, 1}, 
     {1, 1, 0, 1, 0},
     {0, 1, 1, 1, 0},
     {1, 1, 1, 1, 0},
     {1, 1, 1, 1, 1},
     {0, 0, 0, 0, 0}};
    cout << maxSquare(mat) << endl;

    return 0;
}

Java

public class GfG     {

    static int maxSquare(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int ans = 0;

        // Create 2d array for tabulation
        int[][] dp = new int[n + 1][m + 1];

        // Fill the dp
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {

                // If square cannot be formed
                if (mat[i][j] == 0) {
                    dp[i][j] = 0;
                    continue;
                }

                // check all 3 sides
                dp[i][j] = 1 + Math.min(dp[i][j + 1],
                                Math.min(dp[i + 1][j], dp[i + 1][j + 1]));

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

        return ans;
    }

    public static void main(String[] args) {
        int[][] mat = {
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

        System.out.println(maxSquare(mat));
    }
}

Python

def maxSquare(mat):
    n = len(mat)
    m = len(mat[0])
    ans = 0

    # Create 2d array for tabulation
    dp = [[0]*(m+1) for _ in range(n+1)]

    # Fill the dp
    for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):

            # If square cannot be formed
            if mat[i][j] == 0:
                dp[i][j] = 0
                continue

            # check all 3 sides
            dp[i][j] = 1 + min(dp[i][j+1], dp[i+1][j], dp[i+1][j+1])

            ans = max(ans, dp[i][j])

    return ans


mat = [
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]

print(maxSquare(mat))

using System;

class GfG
{
    static int MaxSquare(int[,] mat)
    {
        int n = mat.GetLength(0);
        int m = mat.GetLength(1);
        int ans = 0;

        // Create 2d array for tabulation
        int[,] dp = new int[n + 1, m + 1];

        // Fill the dp
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                // If square cannot be formed
                if (mat[i, j] == 0)
                {
                    dp[i, j] = 0;
                    continue;
                }

                // check all 3 sides
                dp[i, j] = 1 + Math.Min(dp[i, j + 1],
                                Math.Min(dp[i + 1, j], dp[i + 1, j + 1]));

                ans = Math.Max(ans, dp[i, j]);
            }
        }

        return ans;
    }

    static void Main()
    {
        int[,] mat = {
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

        Console.WriteLine(MaxSquare(mat));
    }
}

JavaScript

function maxSquare(mat) {
    let n = mat.length, m = mat[0].length;
    let ans = 0;

    // Create 2d array for tabulation
    let dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // Fill the dp
    for (let i = n - 1; i >= 0; i--) {
        for (let j = m - 1; j >= 0; j--) {

            // If square cannot be formed
            if (mat[i][j] === 0) {
                dp[i][j] = 0;
                continue;
            }

            // check all 3 sides
            dp[i][j] = 1 + Math.min(dp[i][j + 1],
                            dp[i + 1][j], dp[i + 1][j + 1]);

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

    return ans;
}

// Driver code
let mat = [
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
];

console.log(maxSquare(mat));

Output

[Expected Approach] - Using Space Optimized DP – O(n × m) Time and O(n) Space

The idea is store the values for the next column only. We can observe that for a given cell (i,j), its value is only dependent on the two cells of the next column and the bottom cell of current column.

C++

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int maxSquare(vector<vector<int>> &mat) {
    int n = mat.size(), m = mat[0].size();
    int ans = 0;

    // dp to store the result 
    vector<int> dp(n + 1, 0);

    int diagonal = 0;

    // Traverse column by column
    for (int j = m - 1; j >= 0; j--) {
        for (int i = n - 1; i >= 0; i--) {

            int tmp = dp[i];

            // If square cannot be formed
            if (mat[i][j] == 0) {
                dp[i] = 0;
            }
            else {
                dp[i] = 1 + min({dp[i], diagonal, dp[i + 1]});
            }

            diagonal = tmp;

            ans = max(ans, dp[i]);
        }
    }

    return ans;
}

int main() {
    vector<vector<int>> mat = 
                    {{0, 1, 1, 0, 1},
                     {1, 1, 0, 1, 0}, 
                     {0, 1, 1, 1, 0},
                     {1, 1, 1, 1, 0},
                     {1, 1, 1, 1, 1},
                     {0, 0, 0, 0, 0}};
    cout << maxSquare(mat) << endl;

    return 0;
}

Java

public class GfG {

    static int maxSquare(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int ans = 0;

        // dp to store the result 
        int[] dp = new int[n + 1];

        int diagonal = 0;

        // Traverse column by column
        for (int j = m - 1; j >= 0; j--) {
            diagonal = 0;
            for (int i = n - 1; i >= 0; i--) {

                int tmp = dp[i];

                // If square cannot be formed
                if (mat[i][j] == 0) {
                    dp[i] = 0;
                }
                else {
                    dp[i] = 1 + Math.min(dp[i],
                                Math.min(diagonal, dp[i + 1]));
                }

                diagonal = tmp;

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

        return ans;
    }

    public static void main(String[] args) {
        int[][] mat = {
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

        System.out.println(maxSquare(mat));
    }
}

Python

def maxSquare(mat):
    n = len(mat)
    m = len(mat[0])
    ans = 0

    # dp to store the result 
    dp = [0] * (n + 1)

    diagonal = 0

    # Traverse column by column
    for j in range(m - 1, -1, -1):
        diagonal = 0
        for i in range(n - 1, -1, -1):

            tmp = dp[i]

            # If square cannot be formed
            if mat[i][j] == 0:
                dp[i] = 0
            else:
                dp[i] = 1 + min(dp[i], diagonal, dp[i + 1])

            diagonal = tmp

            ans = max(ans, dp[i])

    return ans

if __name__ == "__main__":
    mat = [
        [0, 1, 1, 0, 1],
        [1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0],
        [1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1],
        [0, 0, 0, 0, 0]
    ]
    
    print(maxSquare(mat))

using System;

class GfG
{
    static int MaxSquare(int[,] mat)
    {
        int n = mat.GetLength(0);
        int m = mat.GetLength(1);
        int ans = 0;

        // dp to store the result 
        int[] dp = new int[n + 1];

        int diagonal = 0;

        // Traverse column by column
        for (int j = m - 1; j >= 0; j--)
        {
            diagonal = 0;
            for (int i = n - 1; i >= 0; i--)
            {
                int tmp = dp[i];

                // If square cannot be formed
                if (mat[i, j] == 0)
                {
                    dp[i] = 0;
                }
                else
                {
                    dp[i] = 1 + Math.Min(dp[i],
                                Math.Min(diagonal, dp[i + 1]));
                }

                diagonal = tmp;

                ans = Math.Max(ans, dp[i]);
            }
        }

        return ans;
    }

    static void Main()
    {
        int[,] mat = {
            {0, 1, 1, 0, 1},
            {1, 1, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {1, 1, 1, 1, 0},
            {1, 1, 1, 1, 1},
            {0, 0, 0, 0, 0}
        };

        Console.WriteLine(MaxSquare(mat));
    }
}

JavaScript

function maxSquare(mat) {
    let n = mat.length, m = mat[0].length;
    let ans = 0;

    // dp to store the result 
    let dp = new Array(n + 1).fill(0);

    let diagonal = 0;

    // Traverse column by column
    for (let j = m - 1; j >= 0; j--) {
        diagonal = 0;
        for (let i = n - 1; i >= 0; i--) {

            let tmp = dp[i];

            // If square cannot be formed
            if (mat[i][j] === 0) {
                dp[i] = 0;
            }
            else {
                dp[i] = 1 + Math.min(dp[i], diagonal, dp[i + 1]);
            }

            diagonal = tmp;

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

    return ans;
}


// Driver code
let mat = [
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [1, 1, 1, 1, 0],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
];

console.log(maxSquare(mat));

Output

Maximum Size Square Sub-Matrix with All 1s

[Naive Approach] - Using Recursion - O(3^(n+m)) Time and O(n+m) Space

[Better Approach - 1] - Using Top-Down DP ( Memoization) - O(n × m) Time and O(n × m) Space

[Better Approach - 2] -Using Bottom-Up DP (Tabulation) – O(n × m) Time and O(n × m) Space

[Expected Approach] - Using Space Optimized DP – O(n × m) Time and O(n) Space

Explore