206. Square Under Budget
A city map is a grid of plots, where grid[i][j] is the cost of building on that plot. A developer wants to buy a square block of plots, s plots wide and s plots tall, so that the total cost of all s * s plots is at most threshold.
Return the largest side length s for which such a square exists somewhere in the grid. If even a single plot costs more than threshold, return 0. All costs are non-negative, so if a square of some size fits within the budget, every smaller square inside it does too.
Example 1
- Input:
- grid = [[2,3,1],[4,0,2],[1,5,3]], threshold = 8
- Output:
- 2
- Explanation:
The 2x2 block in rows 0-1, columns 1-2 costs 3+1+0+2 = 6, within budget 8. The whole 3x3 grid costs 21, so the largest side is 2.
Example 2
- Input:
- grid = [[9]], threshold = 4
- Output:
- 0
- Explanation:
The only plot costs 9, more than the budget of 4, so no square fits.
Example 3
- Input:
- grid = [[1,1],[1,1]], threshold = 4
- Output:
- 2
- Explanation:
The whole 2x2 grid costs exactly 4, which is allowed.
Constraints
1 ≤ grid.length, grid[0].length ≤ 500
0 ≤ grid[i][j] ≤ 100
0 ≤ threshold ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(m × n)
- Space
- O(m × n)