Sum of all submatrix from a given matrix approach 2

#1

what would be the time complexity for creating prefix sum array?

#2

Hello @mahima in this we will make use of prefix array to compute the sum in O(1)
and total 4 nested loops therefore time complexity is O(n^4).

#3

yes that’s clear to me. My query is what would be the time complexity for generating prefix sum matrix? We need to run 2 for loops twice to create the prefix sum array - once to calculate it row wise then second time for column wise

#4

so total time complexity of the program would be - O(n^4) + O(n^2) + O(n^2) ?? and space complexity as O(n^2)

#5

@mahima yes right.
for generating prefix sum array for both will be:O(n^2) for each prefix matrix.

#6

can you please share the code link for this approach?

#7

@mahima check this:


Happy Learning!!

#8

Thanks for the help.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#10

can we save the O(n^2) space complexity by saving the prefix sum matrix in the same 2d array? I mean why do we need to create another extra array for it when we can do the same in the given array only?

#12

Please mention the name of the problem you are enquiring about …

#13

sum of all submatrix from a given matrix approach 2 (in which we need to create prefix sum matrix)

#14

in this approach we are having O(n^2) space complexity for storing the prefix sum matrix so can’t we save that space by doing the changes in the same input array?

#15

We are doing same, for eg:if our

Input array is: 
1 2 3 
4 5 6 
7 8 9 
then, Input array after calculating prefix sum row wise is: 
1 3 6 
4 9 15 
7 15 24 
Now same Input array after calculating prefix sum col wise is: 
1 3 6 
5 12 21 
12 27 45 
Therefore total sum can now be calculated using 4 loops 
so constant space is used.