1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – D.W. Jan 25 '16 at 7:23
  • $\begingroup$ 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"? $\endgroup$ – Rafael Medeiros Jan 26 '16 at 3:25
  • $\begingroup$ 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 :) $\endgroup$ – Rafael Medeiros Jan 26 '16 at 3:32
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Incidentally, lovely exercise! Since it's your exercise, I'm going to wait to answer it, to give you the chance to work on it yourself, and to avoid spoiling any ongoing programming contests or assignments. I do hope you'll cite the source for this, so that we can give credit where credit is due! $\endgroup$ – D.W. Jan 25 '16 at 22:21
  • $\begingroup$ It was an online job interview at HackerRank that I applied on Jan 22nd, and I didn't finish this one question, can't submit anymore against the original test cases. It would be unethical to divulge the exact job position for it would spoil the element of surprise they are relying on. There was also a performance requirement in seconds, meaning they wouldn't accept brute force for an answer. I'll spend some more time soon in your suggestion, probably this weekend. Thanks a lot! $\endgroup$ – Rafael Medeiros Jan 26 '16 at 3:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.