Skip to the code
cf.
+50 XP

#50 Heatmap Blocks Hitting a Target

hard

A heatmap widget shows a grid of net changes, grid, which can be negative. A block is any rectangle of one or more neighboring cells.

Write targetBlocks(grid, target) that returns how many blocks have cells adding up to exactly target. Blocks at different positions or of different sizes count separately.

Example 1

Input: grid = [[1,0,1],[0,-1,0]], target = 0
Output: 5

The three cells holding 0 add up to 0, and so do the two 2 by 2 blocks (1 + 0 + 0 - 1).

Example 2

Input: grid = [[2,1],[1,2]], target = 3
Output: 4

The four pairs of side-by-side or stacked cells each add up to 3.

Constraints

  • 1 <= rows, cols <= 60
  • -1000 <= grid[r][c] <= 1000
  • -10^8 <= target <= 10^8
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).