A vineyard field is an m x n grid depth of non-negative integers: the depth of good soil (in decimetres) under each plot. An inspector gives the field a rating: the largest k such that some k x k block of plots (lined up with the grid, fully inside it) has soil depth at least k in every one of its plots.
Return the rating. If every plot has depth 0, the rating is 0.
Examples
Input: depth = [[3, 3, 1], [3, 3, 3], [1, 3, 3]]
Output: 2
Explanation: the top-left 2 x 2 block has depth 3 >= 2 everywhere. The only
3 x 3 block contains a 1.
Input: depth = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Output: 1
Explanation: a 3 x 3 block would need depth at least 3.
Input: depth = [[0, 0], [0, 0]]
Output: 0
Constraints
1 <= m, n <= 5000 <= depth[r][c] <= 10**9
Goals
- Notice that a threshold condition 'every cell at least k' changes with k, so one sweep is not enough
- Prove the yes/no question is monotone in k and binary search on it
- Answer each yes/no question with the largest-square sweep over a 0/1 view of the grid