Data Structures and Algorithms(DSA) Concept- 2D Matrix -Part 2
Topics : Summation of 2D matrix .
Submatrix
A part of the matrix is called a submatrix. A single element is a sub matrix , a complete matrix is also a sub matrix of itself.
Every submatrix is a rectangle.
Q 1. Given a matrix & Q queries . Each Query having a TL(Top left : r1,c1) and BR(bottom right : r2,c2) of a submatrix for every query . Find the sum of every sub matrix from TL to BR.
Eg :
A =[
[ 3, 2, 4, 1, 6 ],
[-1, 4, 3, 2, 4 ],
[ 2, 7, 6, 3, 2 ],
[ 1, 2, 7, 8, 1 ]
]
// TL BR
// r1,c1 r2,c2
Q= [
[ 1, 1, 3, 3 ],
[ 1, 2, 2, 4 ],
[ 2, 1, 3, 1 ]
]
TL BR
r1,c1 r2,c2 SUM
(1,1) (3,3) 42
(1,2) (2,4) 20
(2,1) (3,1) 9
//
Lets see ways we can approach this question.
Approach 1 : Brute Force
For every Sub matrix iterate on all elements and keep adding the values to sum.
TC : O (QxNxM)
SC : O (1)
Please try to implement this approach on your own ,remember more
effort you put in more reward you reap.
Approach 2 : Using prefix Sum.
step 1:
Build Prefix sum on every row
// PS is prefix sum of row of matrix A
PS=[
[ 3, 5, 9, 10, 16 ],
[-1, 3, 6, 8, 12 ],
[ 2, 9, 15, 18, 20 ],
[ 1, 3, 10, 18, 19 ]
]
TC : O(NxM)
step 2 :
Build Prefix sum on column on PS
PS =[
[ 3, 5, 9, 10, 16 ],
[ 2, 8, 15, 18, 28 ],
[ 4, 17, 30, 36, 48 ],
[ 5, 20, 40, 54, 67 ]
]
Case 1 :
TL BR
(1,1) (3,3)
r1,c1 r2,c2
//In the prefix sum matrix
sum of subarray = PS[r2][c2]-PS[r1-1][c2]-PS[r2][c1-1]+PS[r1-1][c1-1]
= PS[3][3] - PS[1-1][3] - PS[3][1-1] + PS[1-1][1-1]
= 54 - 10 - 5 + 3
= 42
Case 2 :
TL BR
(2,0) (1,4)
r1,c1 r2,c2
sum of subarray = PS[r2][c2] -PS[r2][c1-1]
= PS[1][4] - PS[1][1]
= 28 - 8
= 20
Case 3 :
TL BR
(2,0) (3,2)
r1,c1 r2,c2
sum of subarray = PS[r2][c2] - PS[r1-1][c2]
= PS[3][2] - PS[2-1][2]
= 40 - 15
= 25
Case 4:
TL BR
(0,0) (2,3)
r1,c1 r2,c2
sum of subarray = PS[r2][c2]
= PS[2][3]
= 18
Lets see how we can write the code keeping all the cases in mind
public void Sum(int [][] A, int[][] Mat){
// A of size [N][M] , Mat of size [Q][4]
// I hope you will be capable of building prefix sum on your own .
// Incase there are any doubts refer my blog on prefix sum .
// reference link at the end of the blog
// Construct the PS matrix [To DO]
for (int i=0;i<q;i++){
int r1 = Mat[i][0];
int c1 = Mat[i][1];
int r2 = Mat[i][2];
int c2 = Mat[i][3];
int sum =PS[r2][c2];
if (c1 != 0){
sum= sum-PS[r2][c1-1];
}
if (r1 !=0){
sum = sum - PS[r1-1][c2];
}
if(c1 !=0 && r1 != 0){
sum = sum + PS[r1-1][c1-1];
}
System.out.println(sum);
}
}TC : O ( NM +Q)
Q 2 . Given a matrix of size N x M . Find sum of all submatrix sums.
//
formula
The count of elements in a matrix can be calculated using :
= (r2-r1+1) x (c2-c1+1)
//
Lets try to find the sum of all submatrix sums by finding out
the number of subarrays an element is a part of.
consider i,j to be the postion of the element in the matrix.
lets assume that i,j is the index of the Bottom right a submatrix
we can see that each element of this submatrix can be the Top Left of
a another submatrix .
so the number of elements in this matrix will be the number for submatrix's
that the element at i,j contribute too.
so the number of elements to the top left of i,j =
= (r2-r1+1) x (c2-c1+1)
= (i - 0 + 1) x (j - 0 + 1)
= (i+1) x(j+1)
Similarly assume element at i,j is the Top left element of a sub matrix ,
Then the number of submatrix's the element at i,j can be Top left of equal
to the number of elements in the submatrix.
= (r2-r1+1) x (c2-c1+1)
= ((N-1)-i+1) x ((M-1)-j+1)
= (N-i)x(M-j)
The product will give use how many submatrix's that element at i,j
is a part of.
No. of sub matrix's = (i+1)(j+1) x (N-i)(M-j)
containing (i,j)
PLEASE TAKE A SAMPLE MATRIX AND DRY RUN THROUGH THE CALCULATIONS TO
UNDERSTAND BETTER.
lets write the code for see this.public long subMatrixSum (int[][] A){
long sum =0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
long TL = (i+1)(j+1);
long BR = (N-i)(M-j);
sum = sum + A[i][j] * (TL * BR);
}
}
return sum;
} Next :
Hope this was helpful , please do like and follow.
