Maximum size square sub-matrix (DP-13)

You are given a binary matrix with 0’s and 1’s. You need to find out the maximum size of a square with all 1’s in it.

Sample Input: {
{ 0, 0, 1, 0, 1, 1 },
{ 0, 1, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1 }
};

Expected Output: 3
Explanation: The maximum size of any square in the matrix with all 1’s is 3.

Algorithm:

The problem can be solved using dynamic programming as it has both optimal substructure and overlapping subproblems.

  1. We create a 2D array DP which will store the results of the sub-problems. We copy the first row and first column of the given matrix to the DP matrix as it is. Because for every cell in the first row and first column, if it has a value 1, then the answer for that subproblem is 1 and if it has value 0, then the maximum sized square submatrix is 0.
  2. DP [i][j] will return the size of the maximum square sub matrix upto row i and column j.
  3. We iterate for all the elements in the given matrix and for each iteration, we do the following.
    If the value of the cell is 1, we take the minimum of DP [i-1][j-1], DP [i-1][j] and DP [i][j-1] and add 1 to the result and store it in DP[i][j].
  4. The final answer is the maximum value in DP matrix.
#include <bits/stdc++.h>
using namespace std;

int helper(vector<vector<int>> mat, int m, int n){
	vector<vector<int>> dp(m, vector<int>(n, 0));
	for(int i=0; i<m; i++){
		dp[i][0] = mat[i][0];
	}
	for(int j=0; j<n; j++){
		dp[0][j] = mat[0][j];
	}
	int max_ = 0;
	for(int i=1; i<m; i++){
		for(int j=1; j<n; j++){
			if(mat[i][j]==1){
				dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))+1;
				max_ = max(max_, dp[i][j]);
			}
		}
	}
	return max_;
}

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

	int m = 8;
	int n = 6;
	cout<<helper(mat, m, n);
	
	return 0;
}

Also, check out another popular interview problem House Robber.

2 comments

Leave a Reply

Your email address will not be published.