Number of submatrices with a particular sum- Answer Explantion

Question

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?

Answer 1

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

Answer 2

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