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.