6
$\begingroup$

Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I want to find the number of submatrices whose entries sum to K.

The best solution I can find has $O(n^4)$ running time. Any ideas how to improve the running time?

$\endgroup$

migrated from stackoverflow.com Nov 19 '13 at 22:24

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ @TharinduRusira The number of matrices is of the order of M^2 where M is the number of elements in the matrix. Hence time complexity is polynomial at most. $\endgroup$ – Abhishek Bansal Nov 19 '13 at 16:47
  • $\begingroup$ yes, all non negative values $\endgroup$ – hello Nov 19 '13 at 17:00
4
$\begingroup$

Here is an O(N3) algorithm (it is valid only for matrices of non-negative values).

  1. Compute prefix sums for each column: B[k][j] = Sum(A[0..k][j]).
  2. For each pair of row indices (p, q):
  3. Apply a two-pointers algorithm for implicit array of values B[q][j]-B[p][j].

Where a two-pointers algorithm advances first pointer while sum of values between pointers is less than desired and advances second one when this sum is greater than desired. When the desired sum is found, advance first pointer (x times) while sum does not change and advance second pointer (y times) while sum does not change (we might need to advance pointers more then once in case of sub-matrix column summing to zero), then add x*y to counter of found sub-matrices and continue.

$\endgroup$
  • $\begingroup$ @AbhishekBansal: No, they are two rows from the original matrix (j is a variable). So the idea is to fix starting and ending rows of the sub-matrix and then solve simpler 1D problem. $\endgroup$ – Evgeny Kluev Nov 19 '13 at 17:21
  • $\begingroup$ The two pointers are the two boundary columns for submatrix right? $\endgroup$ – Abhishek Bansal Nov 19 '13 at 17:28
  • $\begingroup$ @AbhishekBansal: that's right. $\endgroup$ – Evgeny Kluev Nov 19 '13 at 17:29
  • $\begingroup$ Anyways Nice idea! (converting 2D problem to 1D) $\endgroup$ – Abhishek Bansal Nov 19 '13 at 17:32
1
$\begingroup$

If you are only interested in sub-matrices beginning with [0][0], it is not hard to get O(n^2) with dynamic programming - save partial sums and use them to build sums of larger sub-matrices.

$\endgroup$
  • 1
    $\begingroup$ no, the sub-matrices can begin with any index $\endgroup$ – hello Nov 19 '13 at 16:48
  • 1
    $\begingroup$ Dynamic programming can still help you - once you know the sum of each matrix beginning at [0][0], the sum of any matrix is the sum of one matrix minus the sum of 3 contained matrices, so can be computed in constant time. There are n^4 sub-matrices, but if all the values in the matrix are positive, you can avoid checking all of the sub-matrices. (for example, if the sum of a sub-matrix is too large, you don't need to check any sub-matrix that contains it). $\endgroup$ – Irit Katriel Nov 19 '13 at 16:52
  • $\begingroup$ Sorry, this answer is too brief for me. I don't see how you're getting to $O(n^2)$ time. You say to "avoid checking all the sub-matrices", but how? How do you reduce the number of possible sub-matrices to $O(n^2)$? It's easy to test each possible sub-matrix in $O(1)$ time, but the hard part is limiting the number of sub-matrices you test to $O(n^2)$. I'm not seeing how to do that. Would you care to edit your answer to explain that part? $\endgroup$ – D.W. Nov 20 '13 at 2:16
1
$\begingroup$

It is easy to achieve $O(n^3 \lg n)$ running time by accumulating partial sums, if all entries of $A$ are positive.

Define the $n\times n$ matrix $B$ so that

$$B[i,j] = \sum_{r=0}^i \sum_{s=0}^j A[r,s].$$

The matrix $B$ can be computed in $O(n^2)$ time, by filling it in iteratively using the following recurrence relation:

$$B[i,j] = B[i,j-1] + \sum_{r=0}^i A[r,j] \qquad \text{(for $j>0$)}.$$

If you precompute the column sums and row sums in advance, the recurrence relation above can be computed in $O(1)$ time per entry of $B$.

Then, once you have the matrix $B$, you can test whether a given submatrix has sum $K$ in $O(1)$ time. In particular, the elements of the submatrix $A[i..i'][j..j']$ sum to $B[i',j']-B[i,j']-B[i',j]+B[i,j]$, which can be computed in $O(1)$ time.

How do you enumerate all submatrices that sum to $K$, given this data structure? It is not entirely trivial, as there are $O(n^4)$ possible submatrices, so enumerating them all will take too long. But if all matrix entries are positive, you can do it in $O(n^3 \lg n)$ time using binary search.

In particular, you enumerate all possible values of $i,i',j$ and then do binary search on $j'$ to find whether there exists a $j'$ such that $B[i',j']-B[i,j']-B[i',j]+B[i,j] = K$, using the fact that $B[i',j']-B[i,j']-B[i',j]+B[i,j]$ is a monotonically strictly increasing function of $j'$ when $i,i',j$ are held fixed.

$\endgroup$

Your Answer

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