Leetcode 1139. Largest 1-Bordered Square
Problem Explanation
Given a two-dimensional grid filled with 0s and 1s, we're tasked with finding the square with the largest area that contains all 1s. We're supposed to find the square subgrid with 1s as all four sides and return the area (i.e., the number of elements) of the largest possible square. If no such square exists, we should return 0.
Approach
The approach to solving this problem is to make two more grids, leftOnes
and topOnes
, to count the consecutive one's in the left and on the top of each element, respectively.
To do this, we must iterate through the original grid. If an element is 1, we add 1 to the left one in leftOnes
and the top one in topOnes
.
Then, for each possible square size (from the smallest to the largest), we check all possible position for the square. If a square has both a top and a left side with only 1s and the size greater or equal to the square size, then this is the maximum square we are looking for.
Java Solution
1 2java 3class Solution { 4 public int largest1BorderedSquare(int[][] grid) { 5 int m = grid.length; 6 int n = grid[0].length; 7 int[][] leftOnes = new int[m][n], topOnes = new int[m][n]; 8 for (int i = 0; i < m; ++i) 9 for (int j = 0; j < n; ++j) 10 if (grid[i][j] > 0) { 11 leftOnes[i][j] = j > 0 ? leftOnes[i][j - 1] + 1 : 1; 12 topOnes[i][j] = i > 0 ? topOnes[i - 1][j] + 1 : 1; 13 } 14 for (int maxSide = Math.min(m, n); maxSide > 0; --maxSide) 15 for (int i = 0; i + maxSide - 1 < m; ++i) 16 for (int j = 0; j + maxSide - 1 < n; ++j) 17 if (Math.min(Math.min(topOnes[i + maxSide - 1][j], topOnes[i + maxSide - 1][j + maxSide - 1]), 18 Math.min(leftOnes[i][j + maxSide - 1], leftOnes[i + maxSide - 1][j + maxSide - 1])) >= maxSide) 19 return maxSide * maxSide; 20 return 0; 21 } 22}
Here, we iterate over each cell in the original grid and count the number of consecutive ones in left and top of each cell and store them in leftOnes
and topOnes
respectively. If the original cell value is 0, it doesn't have '1' to its left or top, thus leftOnes
and topOnes
at the [i][j] index, where i and j are the current coordinates, are set to 0.
Next, we iterate each possible square size from the min possible value of m and n to 0 and check all possible positions to place the square on the grid. If a square of size sz
is bordered with 1s all around, we return the area of the square, which is sz*sz as the output.
Python Solution
1 2python 3class Solution(object): 4 def largest1BorderedSquare(self, grid): 5 m, n, res = len(grid), len(grid[0]), 0 6 top, left = [[0]*n for _ in range(m)], [[0]*n for _ in range(m)] 7 for i in range(m): 8 for j in range(n): 9 if grid[i][j] == 0: continue 10 top[i][j] = 1 if i == 0 else top[i-1][j] + 1 11 left[i][j] = 1 if j == 0 else left[i][j-1] + 1 12 for k in range(min(top[i][j], left[i][j]), 0, -1): 13 if top[i][j-k+1] >= k and left[i-k+1][j] >= k: 14 res = max(res, k) 15 break 16 return pow(res, 2)
The Python solution follows a similar approach. After forming the topOnes
and leftOnes
grids, it iterates over each cell and checks the maximum size square that it can border, updating the result res
as necessary. This is done until the maximum size has been decreased to 0, at which point the function returns res
squared, which represents the largest square grid bordered by 1s.## Javascript Solution
1 2javascript 3var largest1BorderedSquare = function(grid) { 4 let m = grid.length; 5 let n = grid[0].length; 6 let topOnes = Array(m).fill(0).map(() => Array(n).fill(0)); 7 let leftOnes = Array(m).fill(0).map(() => Array(n).fill(0)); 8 for (let i = 0; i < m; ++i) 9 for (let j = 0; j < n; ++j) 10 if (grid[i][j] > 0) { 11 leftOnes[i][j] = j > 0 ? leftOnes[i][j - 1] + 1 : 1; 12 topOnes[i][j] = i > 0 ? topOnes[i - 1][j] + 1 : 1; 13 } 14 for (let maxSide = Math.min(m, n); maxSide > 0; --maxSide) 15 for (let i = 0; i + maxSide - 1 < m; ++i) 16 for (let j = 0; j + maxSide - 1 < n; ++j) 17 if (Math.min(Math.min(topOnes[i + maxSide - 1][j], topOnes[i + maxSide - 1][j + maxSide - 1]), 18 Math.min(leftOnes[i][j + maxSide - 1], leftOnes[i + maxSide - 1][j + maxSide - 1])) >= maxSide) 19 return maxSide * maxSide; 20 return 0; 21};
This JavaScript solution follows the same approach as the Java and Python solutions. First, it generates leftOnes and topOnes array. For each cell where grid[i][j] > 0, it counts how many 1s are on the left and up of the cell. And it stores those counts into corresponding cells in topOnes and leftOnes.
Then, it iterates through potential square sizes. For each possible square size, it searches all potential top-left positions of the square to find such a position where the square is bordered by 1s entirely.
If such a square is found, it returns its area. If it is not found in the current iteration, it decreases the size of the potential square and tries again, until the size becomes 0, at which point it returns 0.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.