Rectangles With a Given Sum

Hard

You get a table of integers grid and a number goal. A rectangle is a non-empty block of cells bounded by rows r1 to r2 and columns c1 to c2, inclusive. Return how many rectangles have cells summing to goal. Two rectangles are different if at least one of their borders differs.

Example 1

grid=[[0, 3], [-3, 0]], goal=0 → 3

The two zero cells and the whole table (0 + 3 - 3 + 0 = 0) sum to 0; every row and column sums to 3 or -3.

Example 2

grid=[[1, 1, 1]], goal=2 → 2

Two 1×2 rectangles sum to 2: the first two cells and the last two.

Example 3

grid=[[5]], goal=-5 → 0

Constraints

1 ≤ len(grid), len(grid[0]) ≤ 150
All rows of grid have the same length
-1000 ≤ grid[i][j] ≤ 1000
-10⁸ ≤ goal ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Matrix Prefix Sum

Similar problems

Complete the Sudoku Hard Richest Plot Under the Cap Hard Four Equal Pieces Hard Turn Every Lamp Off Hard Cutting a Berry Cake Hard

Input

grid=[[0, 3], [-3, 0]], goal=0

Expected

Run checks the first 3 tests in your browser. Submit checks all 85 tests on the server, hidden ones included.