Welcome to Subscribe On Youtube

1139. Largest 1-Bordered Square

Description

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

 

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

 

Constraints:

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1

Solutions

Solution 1: Prefix Sum + Enumeration

We can use the prefix sum method to preprocess the number of consecutive 1s down and to the right of each position, denoted as down[i][j] and right[i][j].

Then we enumerate the side length $k$ of the square, starting from the largest side length. Then we enumerate the upper left corner position $(i, j)$ of the square. If it meets the condition, we can return $k^2$.

The time complexity is $O(m \times n \times \min(m, n))$, and the space complexity is $O(m \times n)$. Here, $m$ and $n$ are the number of rows and columns of the grid, respectively.

• Java
• C++
• Python
• Go

• class Solution {
      public int largest1BorderedSquare(int[][] grid) {
          int m = grid.length, n = grid[0].length;
          int[][] down = new int[m][n];
          int[][] right = new int[m][n];
          for (int i = m - 1; i >= 0; --i) {
              for (int j = n - 1; j >= 0; --j) {
                  if (grid[i][j] == 1) {
                      down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                      right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                  }
              }
          }
          for (int k = Math.min(m, n); k > 0; --k) {
              for (int i = 0; i <= m - k; ++i) {
                  for (int j = 0; j <= n - k; ++j) {
                      if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                          && down[i][j + k - 1] >= k) {
                          return k * k;
                      }
                  }
              }
          }
          return 0;
      }
  }
  

• class Solution {
  public:
      int largest1BorderedSquare(vector<vector<int>>& grid) {
          int m = grid.size(), n = grid[0].size();
          int down[m][n];
          int right[m][n];
          memset(down, 0, sizeof down);
          memset(right, 0, sizeof right);
          for (int i = m - 1; i >= 0; --i) {
              for (int j = n - 1; j >= 0; --j) {
                  if (grid[i][j] == 1) {
                      down[i][j] = i + 1 < m ? down[i + 1][j] + 1 : 1;
                      right[i][j] = j + 1 < n ? right[i][j + 1] + 1 : 1;
                  }
              }
          }
          for (int k = min(m, n); k > 0; --k) {
              for (int i = 0; i <= m - k; ++i) {
                  for (int j = 0; j <= n - k; ++j) {
                      if (down[i][j] >= k && right[i][j] >= k && right[i + k - 1][j] >= k
                          && down[i][j + k - 1] >= k) {
                          return k * k;
                      }
                  }
              }
          }
          return 0;
      }
  };
  

• class Solution:
      def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
          m, n = len(grid), len(grid[0])
          down = [[0] * n for _ in range(m)]
          right = [[0] * n for _ in range(m)]
          for i in range(m - 1, -1, -1):
              for j in range(n - 1, -1, -1):
                  if grid[i][j]:
                      down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1
                      right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
          for k in range(min(m, n), 0, -1):
              for i in range(m - k + 1):
                  for j in range(n - k + 1):
                      if (
                          down[i][j] >= k
                          and right[i][j] >= k
                          and right[i + k - 1][j] >= k
                          and down[i][j + k - 1] >= k
                      ):
                          return k * k
          return 0
  
  

• func largest1BorderedSquare(grid [][]int) int {
  	m, n := len(grid), len(grid[0])
  	down := make([][]int, m)
  	right := make([][]int, m)
  	for i := range down {
  		down[i] = make([]int, n)
  		right[i] = make([]int, n)
  	}
  	for i := m - 1; i >= 0; i-- {
  		for j := n - 1; j >= 0; j-- {
  			if grid[i][j] == 1 {
  				down[i][j], right[i][j] = 1, 1
  				if i+1 < m {
  					down[i][j] += down[i+1][j]
  				}
  				if j+1 < n {
  					right[i][j] += right[i][j+1]
  				}
  			}
  		}
  	}
  	for k := min(m, n); k > 0; k-- {
  		for i := 0; i <= m-k; i++ {
  			for j := 0; j <= n-k; j++ {
  				if down[i][j] >= k && right[i][j] >= k && right[i+k-1][j] >= k && down[i][j+k-1] >= k {
  					return k * k
  				}
  			}
  		}
  	}
  	return 0
  }
  

All Problems

All Solutions