Largest Square Within Budget
MediumMatrix
Problem
A developer is buying a square lot from an m × n grid of parcels, where grid[r][c] is the non-negative price of one parcel. The lot must be an axis-aligned square of parcels whose total price is at most budget.
Return the largest possible side length of such a square, or 0 if not even a single parcel is affordable.
Example 1
- Input:
- grid = [[1, 1, 3, 2, 4, 3, 2], [1, 1, 3, 2, 4, 3, 2], [1, 1, 3, 2, 4, 3, 2]], budget = 4
- Output:
- 2
The 2 × 2 square in the top-left corner costs 4. Every 3 × 3 square costs at least 15.
Example 2
- Input:
- grid = [[2, 2, 2], [2, 2, 2]], budget = 1
- Output:
- 0
Every parcel costs more than the budget.
Constraints
- 1 ≤ m, n ≤ 300
- 0 ≤ grid[i][j] ≤ 10^4
- 0 ≤ budget ≤ 10^5
Hint
Show the first hint
With a 2-D prefix table, any square's price is O(1). How many squares are there to try?
Walkthrough
How to approach it
01Clarify before coding
- Are prices non-negative? Yes, which makes cost monotone in the square's size.
- Is a 1 × 1 square allowed? Yes; return 0 only when no parcel is affordable.
- Can the grid be rectangular? Yes; the side cannot exceed min(m, n).
02Brute force
With a prefix table, try every top-left corner and every side length, computing each square's price in O(1).
Cost: O(m · n · min(m, n)): about 2.7 · 10^7 checks for 300 × 300. Binary search on the side improves it to O(m · n · log min(m, n)).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.