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)$

  • $\begingroup$ "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 $\endgroup$ – John L. Oct 23 '18 at 6:50
  • $\begingroup$ 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). $\endgroup$ – zbh2047 Oct 23 '18 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.