Grid Blocks Summing to Target
HardArrays & Hashing
Problem
A farm is divided into a grid of plots, and grid[r][c] is the net yield of a plot (negative when it lost money). A buyer wants to purchase one axis-aligned rectangular block of plots with a total net yield of exactly target.
Return the number of distinct non-empty rectangular blocks (choice of top row, bottom row, left column, right column) whose sum equals target.
Example 1
- Input:
- grid = [[1, -1], [-1, 1]], target = 0
- Output:
- 5
Both rows, both columns and the whole 2×2 grid sum to 0.
Example 2
- Input:
- grid = [[0, 1, 0], [1, 1, 1], [0, 1, 0]], target = 0
- Output:
- 4
Only the four corner plots; every larger block contains a 1.
Constraints
- 1 ≤ rows, cols ≤ 100
- -1000 ≤ grid[r][c] ≤ 1000
- -10^8 ≤ target ≤ 10^8
Hint
Show the first hint
If the grid had a single row, this would be 'count subarrays with sum k'. Can you reduce the 2-D problem to that?
Walkthrough
How to approach it
01Clarify before coding
- Are blocks distinguished by position? Yes: two blocks with identical values in different places both count.
- Can values be negative? Yes, so no window shrinking or pruning by sign.
- What are the grid sizes? Up to 100×100, so an O(R² · C) algorithm (10^6) is the target.
02Brute force
Enumerate all O(R² · C²) rectangles and get each sum in O(1) from a 2-D prefix table.
Cost: O(R² · C²) time: 10^8 rectangles for a 100×100 grid, too slow (and O(R³C³) without the prefix table).
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.