Largest Cross Bordered Square

Last Updated : 11 Nov, 2024

Given a matrix mat[][] of size n x n where every element is either 'O' or 'X', the task is to find the size of the largest square subgrid that is completely surrounded by 'X', i.e. the largest square where all its border cells are 'X'.

Examples:

Input: mat[][] = [ ['X', 'X'],
['X', 'X'] ]
Output: 2
Explanation: The largest square submatrix surrounded by 'X' is the whole input matrix.
Input: mat[][] = [ ['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
Explanation: The square submatrix starting at (1, 1) is the largest submatrix surrounded by 'X'.

Table of Content

Using Brute Force Method - O(n^4) Time and O(1) Space

The idea is to iterate over each cell in the mat[][] and consider it as the top-left corner of potential square submatrices. For each starting cell, we’ll expand the square's size and check if the borders of that square consist entirely of 'X'. If they do, update the maximum size found.

C++

#include <bits/stdc++.h> using namespace std; int largestSubsquare(vector<vector<char>>& mat) {  int n = mat.size();  int maxSize = 0;  // Traverse each cell in the matrix  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  // For each cell (i, j), consider it as the  // top-left corner of squares of increasing sizes  for (int size = 1; size <= n - max(i, j); size++) {  // Check if the square of 'size' with top-left  // corner (i, j) has its borders as 'X'  bool valid = true;  // Check top and left side of the current square  for (int k = 0; k < size; k++) {  if (mat[i][j + k] != 'X' || mat[i + k][j] != 'X') {  valid = false;  break;  }  }  // Check bottom and right sides of   // the current square  for (int k = 0; k < size; k++) {  if (mat[i + size - 1][j + k] != 'X'   || mat[i + k][j + size - 1] != 'X') {  valid = false;  break;  }  }  // If the current square is valid,  // update the maximum size found  if (valid) {  maxSize = max(maxSize, size);  }  }  }  }  return maxSize; } int main() {    vector<vector<char>> mat =  {{'X','X','X','O'},  {'X','O','X','X'},  {'X','X','X','O'},  {'X','O','X','X'}};  cout << largestSubsquare(mat); }

Java

// Java program to find the largest // subsquare with 'X' borders import java.util.Arrays; class GfG {  static int largestSubsquare(char[][] mat) {  int n = mat.length;  int maxSize = 0;  // Traverse each cell in the matrix  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  // For each cell (i, j), consider it as the  // top-left corner of squares of increasing  // sizes  for (int size = 1;  size <= n - Math.max(i, j); size++) {  // Check if the square of 'size' with  // top-left corner (i, j) has its  // borders as 'X'  boolean valid = true;  // Check top and left side of the  // current square  for (int k = 0; k < size; k++) {  if (mat[i][j + k] != 'X'  || mat[i + k][j] != 'X') {  valid = false;  break;  }  }  // Check bottom and right sides of the  // current square  for (int k = 0; k < size; k++) {  if (mat[i + size - 1][j + k] != 'X'  || mat[i + k][j + size - 1]  != 'X') {  valid = false;  break;  }  }  // If the current square is valid,  // update the maximum size found  if (valid) {  maxSize = Math.max(maxSize, size);  }  }  }  }  return maxSize;  }  public static void main(String[] args) {    char[][] mat = { { 'X', 'X', 'X', 'O' },  { 'X', 'O', 'X', 'X' },  { 'X', 'X', 'X', 'O' },  { 'X', 'O', 'X', 'X' } };  System.out.println(largestSubsquare(mat));  } }

Python

# Python program to find the largest # subsquare with 'X' borders def largestSubsquare(mat): n = len(mat) maxSize = 0 # Traverse each cell in the matrix for i in range(n): for j in range(n): # For each cell (i, j), consider it as the # top-left corner of squares of increasing sizes for size in range(1, n - max(i, j) + 1): # Check if the square of 'size' with top-left # corner (i, j) has its borders as 'X' valid = True # Check top and left side of the current square for k in range(size): if mat[i][j + k] != 'X' or mat[i + k][j] != 'X': valid = False break # Check bottom and right sides of the current square for k in range(size): if mat[i + size - 1][j + k] != 'X' or \ mat[i + k][j + size - 1] != 'X': valid = False break # If the current square is valid, # update the maximum size found if valid: maxSize = max(maxSize, size) return maxSize if __name__ == "__main__": mat = [ ['X', 'X', 'X', 'O'], ['X', 'O', 'X', 'X'], ['X', 'X', 'X', 'O'], ['X', 'O', 'X', 'X'] ] print(largestSubsquare(mat))

// C# program to find the largest  // subsquare with 'X' borders using System; class GfG {  static int largestSubsquare(char[][] mat) {    int n = mat.Length;  int maxSize = 0;  // Traverse each cell in the matrix  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  // For each cell (i, j), consider it as the  // top-left corner of squares of increasing  // sizes  for (int size = 1;  size <= n - Math.Max(i, j); size++) {  // Check if the square of 'size' with  // top-left corner (i, j) has its  // borders as 'X'  bool valid = true;  // Check top and left side of the  // current square  for (int k = 0; k < size; k++) {  if (mat[i][j + k] != 'X'  || mat[i + k][j] != 'X') {  valid = false;  break;  }  }  // Check bottom and right sides of the  // current square  for (int k = 0; k < size; k++) {  if (mat[i + size - 1][j + k] != 'X'  || mat[i + k][j + size - 1]  != 'X') {  valid = false;  break;  }  }  // If the current square is valid,  // update the maximum size found  if (valid) {  maxSize = Math.Max(maxSize, size);  }  }  }  }  return maxSize;  }  static void Main() {  char[][] mat = { new char[] { 'X', 'X', 'X', 'O' },  new char[] { 'X', 'O', 'X', 'X' },  new char[] { 'X', 'X', 'X', 'O' },  new char[] { 'X', 'O', 'X', 'X' } };  Console.WriteLine(largestSubsquare(mat));  } }

JavaScript

// JavaScript program to find the largest subsquare with 'X' // borders function largestSubsquare(mat) {  let n = mat.length;  let maxSize = 0;  // Traverse each cell in the matrix  for (let i = 0; i < n; i++) {  for (let j = 0; j < n; j++) {  // For each cell (i, j), consider it as the  // top-left corner of squares of increasing  // sizes  for (let size = 1; size <= n - Math.max(i, j);  size++) {  // Check if the square of 'size' with  // top-left corner (i, j) has its borders as  // 'X'  let valid = true;  // Check top and left side of the current  // square  for (let k = 0; k < size; k++) {  if (mat[i][j + k] !== "X"  || mat[i + k][j] !== "X") {  valid = false;  break;  }  }  // Check bottom and right sides of the  // current square  for (let k = 0; k < size; k++) {  if (mat[i + size - 1][j + k] !== "X"  || mat[i + k][j + size - 1] !== "X") {  valid = false;  break;  }  }  // If the current square is valid,  // update the maximum size found  if (valid) {  maxSize = Math.max(maxSize, size);  }  }  }  }  return maxSize; } const mat = [  [ "X", "X", "X", "O" ], [ "X", "O", "X", "X" ],  [ "X", "X", "X", "O" ], [ "X", "O", "X", "X" ] ]; console.log(largestSubsquare(mat));

Output

Using DP and Prefix Sum - O(n^3) Time and O(n^2) Space

The idea is to use two auxiliary matrices right[][] and down[][], which will store the number of continuous 'X's to the right and bottom for each cell, respectively. This approach allows us to quickly determine the largest square that has borders of 'X' around it.

Step by step approach:

Precompute right and down matrices. right[i][j] will store the number of consecutive 'X's to the right starting from (i, j). down[i][j] will store the number of consecutive 'X's downwards starting from (i, j).
For each cell (i, j), the potential maximum side length of a square with its top-left corner at (i, j) will be the minimum of right[i][j] and down[i][j].
Starting from the maximum possible side length and going downwards, check if this side length is feasible by confirming that the right and down values at the necessary corners meet the side length requirement.

Illustration:

C++

// C++ program to find the largest // subsquare with 'X' borders #include <bits/stdc++.h> using namespace std; int largestSubsquare(vector<vector<char>> &mat) {  int n = mat.size();  // Matrices to store count of 'X' to the right  // and bottom of cells.  vector<vector<int>> right(n, vector<int>(n, 0));  vector<vector<int>> down(n, vector<int>(n, 0));  // Fill the right and down matrices  for (int i = n - 1; i >= 0; i--) {  for (int j = n - 1; j >= 0; j--) {  if (mat[i][j] == 'X') {  right[i][j] = (j == n - 1) ? 1 : right[i][j + 1] + 1;  down[i][j] = (i == n - 1) ? 1 : down[i + 1][j] + 1;  }  }  }  int maxSize = 0;  // Check each cell as the top-left corner of the square  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  // Calculate the maximum possible side  // length for the square starting at (i, j)  int maxSide = min(right[i][j], down[i][j]);  // Iterate from the maximum side length down to 1  for (int side = maxSide; side > 0; side--) {  // Check if the square of length  // 'side' has valid borders  if (right[i + side - 1][j] >= side &&   down[i][j + side - 1] >= side) {  maxSize = max(maxSize, side);  break;  }  }  }  }  return maxSize; } int main() {    vector<vector<char>> mat = {  {'X', 'X', 'X', 'O'},   {'X', 'O', 'X', 'X'},   {'X', 'X', 'X', 'O'},   {'X', 'O', 'X', 'X'}};  cout << largestSubsquare(mat); }

Java

// Java program to find the largest // subsquare with 'X' borders class GfG {  static int largestSubsquare(char[][] mat) {  int n = mat.length;  // Matrices to store count of 'X' to the right  // and bottom of cells.  int[][] right = new int[n][n];  int[][] down = new int[n][n];  // Fill the right and down matrices  for (int i = n - 1; i >= 0; i--) {  for (int j = n - 1; j >= 0; j--) {  if (mat[i][j] == 'X') {  right[i][j] = (j == n - 1)  ? 1  : right[i][j + 1] + 1;  down[i][j] = (i == n - 1)  ? 1  : down[i + 1][j] + 1;  }  }  }  int maxSize = 0;  // Check each cell as the top-left corner of the  // square  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  // Calculate the maximum possible side  // length for the square starting at (i, j)  int maxSide  = Math.min(right[i][j], down[i][j]);  // Iterate from the maximum side length down  // to 1  for (int side = maxSide; side > 0; side--) {  // Check if the square of length  // 'side' has valid borders  if (right[i + side - 1][j] >= side  && down[i][j + side - 1] >= side) {  maxSize = Math.max(maxSize, side);  break;  }  }  }  }  return maxSize;  }  public static void main(String[] args) {    char[][] mat = { { 'X', 'X', 'X', 'O' },  { 'X', 'O', 'X', 'X' },  { 'X', 'X', 'X', 'O' },  { 'X', 'O', 'X', 'X' } };  System.out.println(largestSubsquare(mat));  } }

Python

# Python program to find the largest # subsquare with 'X' borders def largestSubsquare(mat): n = len(mat) # Matrices to store count of 'X' to the right # and bottom of cells. right = [[0] * n for _ in range(n)] down = [[0] * n for _ in range(n)] # Fill the right and down matrices for i in range(n - 1, -1, -1): for j in range(n - 1, -1, -1): if mat[i][j] == 'X': right[i][j] = 1 if j == n - 1 else right[i][j + 1] + 1 down[i][j] = 1 if i == n - 1 else down[i + 1][j] + 1 maxSize = 0 # Check each cell as the top-left # corner of the square for i in range(n): for j in range(n): # Calculate the maximum possible side # length for the square starting at (i, j) maxSide = min(right[i][j], down[i][j]) # Iterate from the maximum side length down to 1 for side in range(maxSide, 0, -1): # Check if the square of length # 'side' has valid borders if right[i + side - 1][j] >= side and \ down[i][j + side - 1] >= side: maxSize = max(maxSize, side) break return maxSize if __name__ == "__main__": mat = [ ['X', 'X', 'X', 'O'], ['X', 'O', 'X', 'X'], ['X', 'X', 'X', 'O'], ['X', 'O', 'X', 'X'] ] print(largestSubsquare(mat))

// C# program to find the largest  // subsquare with 'X' borders using System; class GfG {  static int largestSubsquare(char[][] mat) {  int n = mat.Length;  // Matrices to store count of 'X' to the right  // and bottom of cells.  int[, ] right = new int[n, n];  int[, ] down = new int[n, n];  // Fill the right and down matrices  for (int i = n - 1; i >= 0; i--) {  for (int j = n - 1; j >= 0; j--) {  if (mat[i][j] == 'X') {  right[i, j] = (j == n - 1)  ? 1  : right[i, j + 1] + 1;  down[i, j] = (i == n - 1)  ? 1  : down[i + 1, j] + 1;  }  }  }  int maxSize = 0;  // Check each cell as the top-left corner of the  // square  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  // Calculate the maximum possible side  // length for the square starting at (i, j)  int maxSide  = Math.Min(right[i, j], down[i, j]);  // Iterate from the maximum side length down  // to 1  for (int side = maxSide; side > 0; side--) {  // Check if the square of length  // 'side' has valid borders  if (right[i + side - 1, j] >= side  && down[i, j + side - 1] >= side) {  maxSize = Math.Max(maxSize, side);  break;  }  }  }  }  return maxSize;  }  static void Main() {    char[][] mat = { new char[] { 'X', 'X', 'X', 'O' },  new char[] { 'X', 'O', 'X', 'X' },  new char[] { 'X', 'X', 'X', 'O' },  new char[] { 'X', 'O', 'X', 'X' } };  Console.WriteLine(largestSubsquare(mat));  } }

JavaScript

// JavaScript program to find the largest subsquare with 'X' // borders function largestSubsquare(mat) {  let n = mat.length;  // Matrices to store count of 'X' to the right  // and bottom of cells.  let right  = Array.from({length : n}, () => Array(n).fill(0));  let down  = Array.from({length : n}, () => Array(n).fill(0));  // Fill the right and down matrices  for (let i = n - 1; i >= 0; i--) {  for (let j = n - 1; j >= 0; j--) {  if (mat[i][j] === "X") {  right[i][j] = (j === n - 1)  ? 1  : right[i][j + 1] + 1;  down[i][j] = (i === n - 1)  ? 1  : down[i + 1][j] + 1;  }  }  }  let maxSize = 0;  // Check each cell as the top-left corner of the square  for (let i = 0; i < n; i++) {  for (let j = 0; j < n; j++) {  // Calculate the maximum possible side  // length for the square starting at (i, j)  let maxSide = Math.min(right[i][j], down[i][j]);  // Iterate from the maximum side length down to  // 1  for (let side = maxSide; side > 0; side--) {  // Check if the square of length  // 'side' has valid borders  if (right[i + side - 1][j] >= side  && down[i][j + side - 1] >= side) {  maxSize = Math.max(maxSize, side);  break;  }  }  }  }  return maxSize; } const mat = [  [ "X", "X", "X", "O" ], [ "X", "O", "X", "X" ],  [ "X", "X", "X", "O" ], [ "X", "O", "X", "X" ] ]; console.log(largestSubsquare(mat));