Skip to content

Instantly share code, notes, and snippets.

@jianminchen

jianminchen/Preprocess matrix to calculate the sum of submatrix

Created January 20, 2018 08:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/d71da51638318fc93c73a5a52c6f926e to your computer and use it in GitHub Desktop.
Save jianminchen/d71da51638318fc93c73a5a52c6f926e to your computer and use it in GitHub Desktop.
Download ZIP
Preprocess the matrix to calculate the sum
Raw
Preprocess matrix to calculate the sum of submatrix
given m*n, define a function to calculate the submatrix,
row 2 -> 3, col 1 - 2 -> O(n^2) submatrix
define a function to calculate ,
subRow * subCol - additions -> 3 * 4 = 12 additions -> make it O(1)
calculateSubMatrixSum(marix, startRow, startCol, endRow, endCol)
{
// go over each row
// go over each col
sum += arr[row, col]
Time complexity (row * col ) O(1)
}
The peer came out the idea to preprocess the matrix.
Preprocessing the sum of elements in each row.
go over the sum for each row
go over the sum from i to n
go over the sum from 0 to i.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment