Number of submatrices with a particular sum- Answer Explantion

I read Evgeny Kluev answer on this and was not able to understand the mechanism. Now let us understand using an example. let us say we have this matrix.

[1  2  3  2   5,
2  4  6  4  10,
3  6  9  6  15,
2  4  6  4  10,
5  10 15 10 25]


Now applying step 1 we get .

[ 1  2  3  2  5 ,
3  6  9  6  15,
6  12 18 12 30,
8  16 24 16 40,
13 26 39 26 65]


Now applying step 2 we get all the possible pair of row indices i.e.

(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)


Now comes the last part of applying two pointer algorithm. Which i am failing to understand.For ex.
Lets take (1,2)

B[2][1] - B[1][1]= 3-1 = 2
B[2][2] - B[1][2]= 6-2 = 4
B[2][3] - B[1][3]= 9-3 = 6
B[2][4] - B[1][4]= 6-2 = 4
B[2][5] - B[1][5]= 15-5 =10


Now how is that helping? I mean on these values if we apply two pointer algorithm what will we achieve? For example i am looking for all occurrences of 36. How do i get close to it. ?

Can anybody carry this forward and explain the solution?

The two-pointer algorithm is described in this post. Given a non-negative sequence $\alpha_1,\ldots,\alpha_n$ and a target sum $S$, we want to find the number of pairs $(i,j)$ such that $\alpha_i + \cdots + \alpha_j = S$. Let's make life a little easier by requiring the sequence to be strictly positive. For each $i$ there is therefore at most one $j$ such that $\alpha_i + \cdots + \alpha_j = S$, and we could find it by enumerating over all $j$ (resulting in an $O(n^2)$ algorithm) or using binary search (this requires $O(n)$ preprocessing, and leads to an $O(n\log n)$ algorithm).

The two-pointer algorithm is very similar but uses data from the $i$th iteration to make the $(i+1)$th iteration faster. Here is one variant For each $i$, we calculate the minimal index $j(i)$ such that $\alpha_i + \cdots + \alpha_{j(i)} \geq S$. The main observation is that $j(i)$ is a non-decreasing sequence, that is, $j(1) \leq \cdots \leq j(n)$. This suggests the following algorithm:

1. Initialize $j(0) = 0$.
2. For each $i$ in turn, calculate $j(i)$ by going over $j = j(i-1),j(i-1)+1,\cdots$ until $\alpha_i + \cdots + \alpha_j \geq S$. We then set $j(i) = j$. If $\alpha_i + \cdots + \alpha_{j(i)} = S$, we have found a subsequence summing to $S$.

This algorithm runs in linear time (basically since the index $j(i)$ keeps increasing) and finds all contiguous subsequences summing to $S$. I'll also let you figure out yourself what to do when some entries could be $0$.

• i am sorry but instead of talking in terms of J(0) and abstract explanation, could you explain with help of an example especially the second part. from the Two-pointer algorithm. Please excuse my n00bness. I am new to this. Apr 15 '15 at 21:41
• and also is my solution correct till here? i mean in taking the row pairs. if yes how do i know i have taken all possible sub matrices possible. Apr 15 '15 at 21:43
• It is a very important skill to be able to handle abstract explanations. The two-pointer algorithm is discussed in many webpages, and you can find pseudocode which you can program and trace to see what's going on. Apr 15 '15 at 21:49
• Regarding the first steps of the algorithm, it is really important that you understand what the algorithm is trying to do. The two-pointer algorithm used in the last step is really an optimization. Suppose that you implemented the last step using the trivial algorithm. Do you see why the algorithm then outputs the correct answer? If not, it is pointless trying to understand the tricky implementation of the last step. First understand the simpler aspects of the algorithm. Apr 15 '15 at 21:50
• Make sure that you understand first why the algorithm works at all (treating the two-pointer algorithm as a black box). Only then can you understand why the algorithm was designed this way. Apr 16 '15 at 19:18

As the values you have computed till now is array C[j] = summation of A[p][j] to A[q][j]. Now if we will be able to find the sub array C[x..y] with sum K then definitely sum of sub matrix A[p..q][x..y] will be K. In step 3 instead of applying two pointer algorithm, we can use this method for finding a sub array with given sum, which works in O(n).