Number of submatrices, of a base matrix derived from an array, with a particular sum

Question

Given an N sized array A of unsorted integers and an integer K, derive a square matrix M of order N where $ M_{ij} = A_i * A_j $, and return the number of sub matrices of M where the sum of all of its elements is K.

Example:

$A = \begin{Bmatrix}1&-1\end{Bmatrix}$
$K = 0$

Thus:
$M = \begin{Bmatrix}1 & -1\\-1 & 1\\\end{Bmatrix}$

So, there are 5 submatrices where the sum of its elements is 0:
$ M_{00}...M_{01} = 1 + (-1) = 0$
$ M_{10}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{10} = 1 + (-1) = 0$
$ M_{01}...M_{11} = (-1) + 1 = 0$
$ M_{00}...M_{11} = (-1) + 1 + (-1) + 1 = 0$

Brute force is obvious and it costs $O(n^4)$, but I'm looking for a less naive solution. The first thing that comes to mind (at least mine) is two pointer algorithm, but it works only when there are no negative members, which is not the case. If it were it would make this question a duplicate of this one.

I believe there is a smarter way to solve this because of the correlation between M and A, but I can't figure out how.

Answer 1

Try writing a small example (e.g., where $N=3$), then pick a submatrix (say, $2 \times 2$) and write an expression for the sum of the elements of that submatrix in terms of the entries of $A$. By doing some algebraic manipulations, you should be able to get a nice expression for this sum.

This will then let you characterize which submatrices sum to $K$, in terms of the entries of $A$. Working on this a bit, you should be able to get a $O(N^2)$ time algorithm [assuming a submatrix is defined by a consecutive range of rows and a consecutive range of columns].

Since this is your exercise/programming contest problem, I'll let you work out the details.