Problem Statement

Given a matrix where every element is either ‘O’ or ‘X’, find the largest subsquare surrounded by ‘X’. In the below article, it is assumed that the given matrix is also a square matrix. The code given below can be easily extended for rectangular matrices.

Examples:

Input: mat[N][N] = { {'X', 'O', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'O', 'X', 'O'},
                     {'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'O'},
                    };
Output: 3
The square submatrix starting at (1, 1) is the largest
submatrix surrounded by 'X'

Input: mat[M][N] = { {'X', 'O', 'X', 'X', 'X', 'X'},
                     {'X', 'O', 'X', 'X', 'O', 'X'},
                     {'X', 'X', 'X', 'O', 'O', 'X'},
                     {'X', 'X', 'X', 'X', 'X', 'X'},
                     {'X', 'X', 'X', 'O', 'X', 'O'},
                    };
Output: 4
The square submatrix starting at (0, 2) is the largest
submatrix surrounded by 'X'

Problem Link

Given a matrix of 'O' and 'X', find the largest subsquare surrounded by 'X' - GeeksforGeeks

Reference Video

https://www.youtube.com/watch?v=vi_1eHCsR9A&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&index=41&ab_channel=TusharRoy-CodingMadeSimpleTusharRoy-CodingMadeSimple

Code

class Solution {
  public:
    int largestSubsquare(int N, vector<vector<char>> A) {
        
        vector<vector<pair<int,int>>> dp(N,vector<pair<int,int>>(N));
        //v,h
        
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(A[i][j]=='O')
                dp[i][j] = {0,0};
                
                else
                {
                    if(!i and !j)
                    dp[i][j] = {1,1};
                    
                    else if(!i and j)
                    dp[i][j] = {1,dp[i][j-1].second+1};
                    
                    else if(i and !j)
                    dp[i][j] = {dp[i-1][j].first+1,1};
                    
                    else
                    dp[i][j] = {dp[i-1][j].first+1,dp[i][j-1].second+1};
                }
                
            }
        }
        int res = 0;
        for(int i=N-1;i>=0;i--)
        {
            for(int j=N-1;j>=0;j--)
            {
                int minD = min(dp[i][j].first,dp[i][j].second);
                if(minD>res)
                {
                    while(minD>0)
                    {
                        if(dp[i][j-minD+1].first>=minD and dp[i-minD+1][j].second>=minD)
                        {
                            res = max(res,minD);
                            break;
                        }
                        minD--;
                    }
                }
            }
        }
        
        return res;
        
    }
};
// Time Complexity : O(n^3)
// Space Complexity : O(n^2)