# Find the Maximum 2D Subarray

Geeks

Maximum size square sub-matrix with all 1s

# Description:

## Example:

``````   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

return 3*3=9
``````

# Idea:

``````1) Construct a sum matrix S[R][C] for the given M[R][C].
a)    Copy first row and first columns as it is from M[][] to S[][]
b)    For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
``````
``````For the given M[R][C] in above example, constructed S[R][C] would be:

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  2  2  0
1  2  2  3  1
0  0  0  0  0
``````

# Code:

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int threeMin(int a, int b, int c){
return min(a, min(b, c));
}

int maxSquareSubarray(vector<vector<int>> matrix){

int rowN=matrix.size();
int columnN=matrix[0].size();

vector<vector<int>> secondMatrix(rowN+1, vector<int>(columnN+1, 0));

for(int i=0; i<rowN; i++){
for(int j=0; j<columnN; j++){
if (matrix[i][j] == 1)
secondMatrix[i+1][j+1]=threeMin(secondMatrix[i][j],
secondMatrix[i+1][j],
secondMatrix[i][j+1])+1;
else
secondMatrix[i+1][j+1]=0;
}
}

int maxArea=0;
for(int i=0; i<rowN; i++){
for(int j=0; j<columnN; j++){
maxArea = max(maxArea, secondMatrix[i+1][j+1]);
}
}

return maxArea*maxArea;
}

int main(){
vector<vector<int>> matrix={
{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<<maxSquareSubarray(matrix);
}
``````