Today we will see the code to get Prefix sum matrix of a 2D matrix .
We calculate the prefix sum by changing the matrix in-place.
For the 0th row and column, prefix sum can be easily calculated by adding the previous sum to the element.
For the other cells, we can find the prefix sum as:
- Add the prefix sum of the cell just above and left to it.
- Subtract the prefix sum of the cell on the top-left diagonal cell. We do this because we have added this prefix sum in each of the top and left cell of the given cell. Therefore, we have to subtract it once.
Fig.Getting prefix sum
Code :
for(int i=0; i<row; i++){ for(int j=0; j<col; j++){ if(i>0) grid[i][j] += grid[i-1][j]; if(j>0) grid[i][j] += grid[i][j-1]; if(i>0 && j>0) grid[i][j] -= grid[i-1][j-1];
} } |
Related question for practice :
https://leetcode.com/problems/count-submatrices-with-top-left-element-and-sum-less-than-k/description/
Comments
Post a Comment