Practice/Meta/Leetcode 1074. Number of Submatrices That Sum to Target

Leetcode 1074. Number of Submatrices That Sum to Target

CodingMust

Problem

Given a 2D integer matrix and a target integer, determine how many non-empty rectangular submatrices exist within the matrix such that the sum of all elements in the submatrix equals the target value.

A submatrix is defined by choosing a contiguous block of rows and columns from the original matrix. The submatrix can be as small as a single cell or as large as the entire matrix.

Requirements

1. Count all possible rectangular regions (submatrices) whose elements sum to the target
2. Each submatrix must be non-empty and contiguous
3. Return the total count of valid submatrices

Constraints

• 1 ≤ matrix.length ≤ 100 (number of rows)
• 1 ≤ matrix[0].length ≤ 100 (number of columns)
• -1000 ≤ matrix[i][j] ≤ 1000
• -10^8 ≤ target ≤ 10^8
• Expected time complexity: O(rows² × cols)
• Expected space complexity: O(cols)

Examples

Example 1:

` Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 Output: 4 Explanation: The four submatrices that sum to 0 are:

• Top-left cell: [0]
• Top-right cell: [0]
• Bottom-left cell: [0]
• Bottom-right cell: [0] `

Example 2:

` Input: matrix = [[1,-1],[-1,1]], target = 0 Output: 5 Explanation: Five submatrices sum to 0:

• Top row: [1,-1]
• Bottom row: [-1,1]
• Left column: [[1],[-1]]
• Right column: [[-1],[1]]
• Entire matrix: [[1,-1],[-1,1]] `

Example 3:

Input: matrix = [[904]], target = 0 Output: 0 Explanation: The single cell has value 904, which does not equal 0.