Loading
Loading
An agronomist divides a field into a grid of cells and records each cell's yield change versus last season, which may be negative. She wants to know how many rectangular plots — any axis-aligned block of whole cells — changed by exactly a target amount.
Given grid and target, return the number of non-empty rectangular sub-grids whose cells sum to exactly target. Plots at different positions count separately even if they overlap.
grid = [[1, 2], [3, 1]], target = 3rows 0..0: column totals [1, 2][1, 2] sums to 3 — one plotrows 1..1: column totals [3, 1][3] alone — one plotrows 0..1: column totals [4, 3]the right column alone — one plot3Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
| 0 | 1 | 2 |
|---|---|---|
| 1 | 3 | 1 |
[1, 2] across the top row, [3] alone, and [2, 1] down the right column.
Example 2
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(rows² · cols) time · O(cols) space
Input. Run your code to watch it work on this input, one line at a time.
| 0 | 1 | 2 |
|---|---|---|
| 1 | 3 | 1 |
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
| 0 | 1 | -1 |
|---|---|---|
| 1 | -1 | 1 |
Both full rows, both full columns, and the whole grid each sum to 0: five plots.