1139. Largest 1-Bordered Square

LeetCode 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

Tags

Dynamic Programming

Solution

For each square, know how many ones are up, left, down, and right of this square. We can use prefix-sum along 2 axes to pre-process for quicker look-up. Now for each square, we can evaluate whether that square is 1-bordered, by checking if the edge length is equal to the sum of the edge elements with prefix-sum in O(1).

Complexity

• Time complexity: $O(n^3)$

• Space complexity: $O(n^2)$

Code

 func largest1BorderedSquare(grid [][]int) int {
	ans, px, py := 0, make([][]int, len(grid)+1), make([][]int, len(grid)+1) // prefix-sum
	for i := range px {
		px[i], py[i] = make([]int, len(grid[0])+1), make([]int, len(grid[0])+1)
	}
	for i := 1; i < len(px); i++ {
		for j := 1; j < len(px[0]); j++ {
			px[i][j], py[i][j] = px[i][j-1]+grid[i-1][j-1], py[i-1][j]+grid[i-1][j-1]
		}
	}
	for i := 1; i < len(px); i++ {
		for j := 1; j < len(px[0]); j++ {
			for k := len(px[0]) - 1; k >= j; k-- {
				l := k - j + 1
				if l <= ans {
					break
				}
				if i+l-1 >= len(px) {
					continue
				}
				if px[i][k]-px[i][j-1] != l {
					continue
				}
				if px[i+l-1][k]-px[i+l-1][j-1] != l {
					continue
				}
				if py[i+l-1][j]-py[i-1][j] != l {
					continue
				}
				if py[i+l-1][k]-py[i-1][k] != l {
					continue
				}
				ans = l
			}
		}
	}
	return ans * ans
}

Reference

1. golang 20ms 简单易懂