Number of Submatrices That Sum to Target

HardMatrixprefix sum

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an integer matrix matrix and an integer target, count the non-empty axis-aligned rectangular submatrices whose elements sum to target. A submatrix is determined by its top row r1, bottom row r2, left column c1, and right column c2 (with r1 <= r2, c1 <= c2); two submatrices are different if any of these four coordinates differ, even when their contents are equal. Aim for O(rows^2 * cols) time.

Examples

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
The four 1x1 submatrices made of the corner zeros.
Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Two 1x2, two 2x1, and the full 2x2 submatrix.
Input: matrix = [[904]], target = 0
Output: 0
The only submatrix sums to 904.

Constraints

  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i][j] <= 1000
  • -10^8 <= target <= 10^8

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More prefix sum problems