Richest Block Under a Cap
HardMatrix
Problem
A land registry divides a region into an m × n grid of plots, where grid[r][c] is the plot's yearly profit (negative for plots that lose money). An investor will buy one non-empty axis-aligned rectangular block of plots, but a regulator forbids any purchase whose total profit exceeds cap.
Return the largest total profit of a block that does not exceed cap. At least one such block is guaranteed to exist.
Example 1
- Input:
- grid = [[1, 0, 1], [0, -2, 3]], cap = 2
- Output:
- 2
The block of columns 1–2 in both rows sums to 0 + 1 - 2 + 3 = 2. Larger blocks exist, but every block summing to 3 or more is forbidden.
Example 2
- Input:
- grid = [[2, 2, -1]], cap = 3
- Output:
- 3
The block [2, 2, -1] sums to exactly 3.
Example 3
- Input:
- grid = [[5, -3]], cap = 4
- Output:
- 2
Candidates are 5, -3 and 2; only -3 and 2 are allowed.
Constraints
- 1 ≤ m, n ≤ 100
- -100 ≤ grid[i][j] ≤ 100
- -10^5 ≤ cap ≤ 10^5
- At least one block sums to at most cap.
Hint
Show the first hint
Fix the top and bottom rows of the block. What does the problem become if you collapse those rows into one array of column sums?
Walkthrough
How to approach it
01Clarify before coding
- Must the block be non-empty? Yes, and at least one valid block exists, so the answer is always defined.
- Can the best block equal cap exactly? Yes, 'not exceed' means ≤ cap.
- Are negative profits possible? Yes, which rules out sliding windows: sums are not monotone in the block's size.
02Brute force
With a 2-D prefix table, enumerate every block (four corners) and compute its sum in O(1).
Cost: O(m² · n²): 10^8 blocks for a 100 × 100 grid, which is too slow.
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.