Getting wrong sum of all submatix

#1

not getting correct answer by approach 2

#2

@Rupesh-1984, your algo for finding prefix sum matrix is wrong , in prefix sum matrix what we do is to make a matrix such that prefixSum[i][j] give us the sum of all the elements in the submatrix with top left index as (0,0) and bottom right index as (i,j) , we do this to find the sum of submatrix in o(1) when the topleft and bottom right indexes of the submatrix are known

Now to find prefix array you can simply use previously computed values to compute prefixSum[i][j]. Unlike 1D array prefix sum, this is tricky, here if we simply add prefixSum[i][j-1] and prefixSum[i-1][j], we get sum of elements from a[0][0] to a[i-1][j-1] twice, so we subtract prefixSum[i-1][j-1].

so , prefixSum[i][j]=prefixSum[i][j-1]+prefixSum[i-1][j]-prefixSum[i-1][j-1]

refer this code for better understanding :- https://ide.codingblocks.com/s/285374

#3

My algo is correct and i know its time taking but but but its correct …

my question is…how i make sum of all submatrix using approach 2…i just did what mentor teach me but i’m getting wrong sum…

Actually i already coded sum of all submatrix using approach 1 and approach 3 but for approach 2 i got stuck bcz answers that are coming out by approach 1 and 3 are same but not for approach 2

and you just provided me prefixsum of matrix but i want all submatrix sum USING APPROACH 2 !!

PLS HELP ME OUT SIR…

#4

there are two issues with your code :-

  1. the formula you are applying is wrong i.e
    sum += arr[bi][bj] - arr[li - 1][bj] - arr[bi][li - 1] + arr[li - 1][lj - 1];
    should be sum += arr[bi][bj] - arr[li - 1][bj] - arr[bi][lj - 1] + arr[li - 1][lj - 1];
  2. you should check for negative index , i.e. li-1 should be always>=0 and lj-1 should be always >=0

corrected code :-

1 Like
#5

THANK YOU SIR NOW I GOT IT WHAT I WAS DOING WRONG