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

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.

• Welcome to CS.SE! 1. Is a "submatrix" defined by a consecutive range of rows and columns? Or is defined by a subset of rows and columns? 2. Can you share the context in which you ran into this? Don't forget to give attribution to your sources. 3. Have you tried some small examples? That's usually a great place to start. Try to find an expression for the relationship between the sum and the entries of A... – D.W. Jan 25 '16 at 7:23
• 2. I run into this in an online interview that took place in hackerrank.com/job for a Software Developer position. I don't think that would be ethical to divulge more than this for they are surely counting on the element of surprise. There were 4 timed questions, two very easy, a tricky one and this, that I didn't finish. I'm not allowed to copy&paste (I could print screen but I didn't try tough) so what I wrote is what I remembered right after the test. I already knew two pointer algorithm but when the example showed negative numbers I was like "kobayashi maru"? – Rafael Medeiros Jan 26 '16 at 3:25
• 1. Now that you've asked I'm not sure, I don't recall either. The only example given is the 2x2 matrix that I put in the statement. But thinking about it now I believe if we limit submatrices to only consecutive ranges, things would become easier. 3. I've searched the whole Sunday for problems that were similar in a way that I could adapt, without success. Now during the week I just haven't got the time but I'll surely try your suggestion as soon as I have no other overdue assignments bleeding my schedule :) – Rafael Medeiros Jan 26 '16 at 3:32

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