954. Capped Rectangle Sum
A solar farm is modelled as a grid grid of panels; each cell holds the net power balance of one panel (negative means the panel drains power). A technician may isolate any non-empty rectangle of contiguous rows and columns and add up its cell values.
Given a cap k, find the largest rectangle sum that does not exceed k and return it. The rectangle must be non-empty, and equal sums from different rectangles are of course the same answer. It is guaranteed that k is at least the smallest cell value, so at least one rectangle (a single cell) always fits under the cap and an answer exists.
Example 1
- Input:
- grid = [[3,-2,4],[-1,5,-3]], k = 5
- Output:
- 5
- Explanation:
The whole grid sums to 6, which is over the cap of 5, but the top row alone (3 - 2 + 4) sums to exactly 5, and no rectangle gives more without exceeding 5.
Example 2
- Input:
- grid = [[5,5],[5,5]], k = 7
- Output:
- 5
- Explanation:
Every single cell is 5, while any larger rectangle sums to 10 or more, so the best sum not above 7 is 5.
Example 3
- Input:
- grid = [[2]], k = 2
- Output:
- 2
- Explanation:
The only rectangle is the single cell, whose sum 2 equals the cap.
Constraints
- 1 ≤ rows ≤ 100, 1 ≤ cols ≤ 1000
- -100 ≤ grid[i][j] ≤ 100
- -105 ≤ k ≤ 105, and k ≥ the minimum cell value of the grid
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(rows^2 * cols * log cols)
- Space
- O(cols)