Matrix Zero Sum Subgrids
MediumPractice library · +20 XPmatrixprefix sumshash map
Given an M x N matrix of integers, find the number of rectangular subgrids whose elements sum to zero. A subgrid is defined by its top-left corner (r1, c1) and its bottom-right corner (r2, c2), where 1 <= r1 <= r2 <= M and 1 <= c1 <= c2 <= N.
Input
The first line contains two integers M and N (1 <= M, N <= 200). The next M lines each contain N integers, where each integer is between -1000 and 1000.
Output
Print a single integer: the total count of subgrids with a sum of zero.
Constraints
1 <= M, N <= 200 -1000 <= matrix[i][j] <= 1000
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
2 2 1 1 1 1
Output
0
No subgrid sums to zero.
Example 2
Input
2 2 1 -1 -1 1
Output
5
Four 1x1 subgrids sum to 1 or -1. Two 1x2 subgrids sum to 0. Two 2x1 subgrids sum to 0. One 2x2 subgrid sums to 0. Total 5.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
2 2 1 1 1 1
Example 2 input
2 2 1 -1 -1 1