# Count submatrices with only zeros for each element of the matrix

Let's say we have given matrix of size $$N \cdot M$$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. We actually want only the sum of those value, not separately for each of them.

For example:

010 -> 201
001 -> 320
The sum is: 3 + 2 + 2 + 1 = 8


I have a solution with complexity of $$O(N^3)$$ which counts all possible rectangles with fixing the lower right corner, but I know that this can be improved somehow to $$O(N^2)$$

• "I know that this can be improved somehow to O(N2)". If this problem comes from an online programming contest or course, could you please add a URL in the question? If it comes from a book or a paper, a reference. Besides paying proper attribute to the original source (we do not want to commit plagiarism), all that information also motivates and helps people answer the question faster and better – John L. Oct 23 '18 at 6:50
• This problem can be found here: 51nod.com/onlineJudge/questionCode.html#!problemId=1291 , which already has solutions. Calculating all n*m values can be done in O(nm). – zbh2047 Oct 23 '18 at 16:15