Number of submatrices with a particular sum

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?

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

• Compute prefix sums for each column: B[k][j] = Sum(A[0..k][j]).

• For each pair of row indices (p, q):

• 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.

StackExchange Computer Science Q#18173, answer score: 4