All problems

Biggest Picnic Square

Medium · prefix sum

The town park has a square lawn, split into a grid of equal patches. The grid lawn has the same number of rows and columns, and lawn[r][c] is the number of molehills on the patch in row r, column c.

You want to lay down one square picnic blanket. A blanket covers a block of whole patches that is s patches wide and s patches tall, and it must lie completely on the lawn. Nobody wants to sit on too many molehills, so a blanket is only acceptable if the total number of molehills on the patches it covers is at most limit.

Return the largest side length s of an acceptable blanket. If not even a single patch is acceptable, return 0.

Examples

Example 1

Input: lawn = [[1, 0, 2], [0, 0, 1], [3, 0, 0]], limit = 1

Output: 2

The top-left 2 by 2 block holds 1 + 0 + 0 + 0 = 1 molehill. The whole 3 by 3 lawn holds 7, which is too many.

Example 2

Input: lawn = [[5, 5], [5, 5]], limit = 4

Output: 0

Every single patch has 5 molehills, which is more than the limit.

Example 3

Input: lawn = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], limit = 0

Output: 3

The lawn has no molehills at all, so the blanket can cover all of it.

Constraints