O( m*n ) sol. based on integral image technique ( 2D DP ).\n\n---\n\n**Explanation on integral image**:\n\nHere we use the technique of **integral image**, which is introduced to **speed up block computation**.\n\nAlso, this technique is practical and common in the field of matrix operation and image processing such as [filtering](https://docs.opencv.org/master/d4/d86/group__imgproc__filter.html#gad533230ebf2d42509547d514f7d3fbc3) and feature extraction.\n\nBlock sum formula on integral image.\n **Block-sum** of **red rectangle** = **block-sum of D - block-sum of B - block-sum of C + block-sum of A**\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1579243522.png)\n\n---\n\n**Example** of integral image ( focus on the purple block ).\n\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1579244254.png)\n\n\n---\n\n**Implementation**:\n\n**Python**:\n\n```\nclass Solution:\n def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n \n h, w = len(mat), len( mat[0])\n integral_image = [ [ 0 for y in range(w) ] for x in range(h) ]\n \n\n # building integral image to speed up block sum computation\n for y in range(0, h):\n summation = 0\n \n for x in range(0, w):\n summation += mat[y][x]\n integral_image[y][x] = summation\n \n if y > 0:\n integral_image[y][x] += integral_image[y-1][x]\n \n \n \n # compute block sum by looking-up integral image\n output_image = [ [ 0 for y in range(w) ] for x in range(h) ]\n \n for y in range(h):\n for x in range(w):\n \n min_row, max_row = max( 0, y-K), min( h-1, y+K)\n min_col, max_col = max( 0, x-K), min( w-1, x+K)\n \n output_image[y][x] = integral_image[max_row][max_col]\n \n if min_row > 0:\n output_image[y][x] -= integral_image[min_row-1][max_col]\n \n if min_col > 0:\n output_image[y][x] -= integral_image[max_row][min_col-1]\n \n if min_col > 0 and min_row > 0:\n output_image[y][x] += integral_image[min_row-1][min_col-1]\n \n return output_image\n```\n\n---\n\n**Javascript**:\n\n```\nvar matrixBlockSum = function(mat, k) {\n \n let [h, w] = [ mat.length, mat[0].length ];\n \n let integralImg = new Array(h).fill(0).map( () => new Array(w).fill(0) );\n let outputImg = new Array(h).fill(0).map( () => new Array(w).fill(0) );\n \n \n // building integral image to speed up block sum computation\n for( let y = 0 ; y < h ; y++){\n let pixelSum = 0;\n \n for( let x = 0 ; x < w ;x++){\n pixelSum += mat[y][x];\n integralImg[y][x] = pixelSum;\n \n if( y > 0 ){ \n integralImg[y][x] += integralImg[y-1][x];\n }\n }\n }\n \n \n // compute block sum by looking-up integral image\n for( let y = 0 ; y < h ; y++){\n \n let [minRow, maxRow] = [ Math.max(0, y-k), Math.min(h-1, y+k)];\n \n for( let x = 0 ; x < w ;x++){\n \n let [minCol, maxCol] = [ Math.max(0, x-k), Math.min(w-1, x+k)];\n \n outputImg[y][x] = integralImg[maxRow][maxCol];\n \n if( minRow > 0 ){\n outputImg[y][x] -= integralImg[minRow-1][maxCol];\n }\n \n if( minCol > 0 ){\n outputImg[y][x] -= integralImg[maxRow][minCol-1];\n }\n \n if( (minRow > 0) && (minCol > 0) ){\n outputImg[y][x] += integralImg[minRow-1][minCol-1];\n }\n \n \n }\n }\n \n return outputImg;\n \n \n};\n```\n\n---\n\n**C++**\n\n```\nclass Solution {\npublic:\n vector> matrixBlockSum(vector>& mat, int k) {\n\n const int h = mat.size(), w = mat[0].size();\n \n vector< vector > integralImg = vector< vector >(h, vector< int >(w, 0) );\n vector< vector > outputImg = vector< vector >(h, vector< int >(w, 0) );\n \n \n // building integral image to speed up block sum computation\n for( int y = 0 ; y < h ; y++){\n int pixelSum = 0;\n \n for( int x = 0 ; x < w ;x++){\n pixelSum += mat[y][x];\n integralImg[y][x] = pixelSum;\n \n if( y > 0 ){ \n integralImg[y][x] += integralImg[y-1][x];\n }\n }\n }\n \n \n // compute block sum by looking-up integral image\n for( int y = 0 ; y < h ; y++){\n \n const int minRow = max(0, y-k), maxRow = min(h-1, y+k);\n \n for( int x = 0 ; x < w ;x++){\n \n const int minCol = max(0, x-k), maxCol = min(w-1, x+k);\n \n outputImg[y][x] = integralImg[maxRow][maxCol];\n \n if( minRow > 0 ){\n outputImg[y][x] -= integralImg[minRow-1][maxCol];\n }\n \n if( minCol > 0 ){\n outputImg[y][x] -= integralImg[maxRow][minCol-1];\n }\n \n if( (minRow > 0) && (minCol > 0) ){\n outputImg[y][x] += integralImg[minRow-1][minCol-1];\n }\n }\n }\n \n return outputImg; \n }\n};\n```\n\n---\n\n**Go**:\n\n```\nfunc create2DArray( h, w int) [][]int{\n \n matrix := make( [][]int, h )\n row := make( []int, h * w)\n \n for y := 0 ; y < h ; y++{\n matrix[ y ] = row[ y*w : (y+1)*w ] \n }\n \n return matrix\n}\n\n\nfunc max(x, y int) int {\n if x > y {\n return x\n }else{\n return y\n }\n}\n\nfunc min(x, y int) int {\n if x < y {\n return x\n }else{\n return y\n }\n}\n\n\n\nfunc matrixBlockSum(mat [][]int, k int) [][]int {\n \n h, w := len(mat), len(mat[0])\n \n integralImg := create2DArray(h, w)\n outputImg := create2DArray(h, w)\n \n \n \n // building integral image to speed up block sum computation\n for y := 0 ; y < h ; y++{\n pixelSum := 0;\n \n for x := 0 ; x < w ;x++{\n pixelSum += mat[y][x];\n integralImg[y][x] = pixelSum;\n \n if y > 0 { \n integralImg[y][x] += integralImg[y-1][x];\n }\n }\n }\n \n \n // compute block sum by looking-up integral image\n for y := 0 ; y < h ; y++{\n \n minRow := max(0, y-k)\n maxRow := min(h-1, y+k)\n \n for x := 0 ; x < w ;x++ {\n \n minCol := max(0, x-k)\n maxCol := min(w-1, x+k)\n \n outputImg[y][x] = integralImg[maxRow][maxCol];\n \n if( minRow > 0 ){\n outputImg[y][x] -= integralImg[minRow-1][maxCol];\n }\n \n if( minCol > 0 ){\n outputImg[y][x] -= integralImg[maxRow][minCol-1];\n }\n \n if( (minRow > 0) && (minCol > 0) ){\n outputImg[y][x] += integralImg[minRow-1][minCol-1];\n }\n }\n }\n \n return outputImg; \n \n\n}\n```\n\n---\n\nShare another implementation with update function in bottom-up\n\n

\n\t

Click to show source code

\n\n```\nclass Solution:\n def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n \n h, w = len(mat), len( mat[0])\n integral_image = [ [ 0 for y in range(w) ] for x in range(h) ]\n \n #-----------------------------------------\n def update(x, y):\n \n # add current pixel\n result = mat[y][x]\n \n if x:\n # add integral image of left pixel\n result += integral_image[y][x-1]\n \n if y:\n # add integral image of top pixel\n result += integral_image[y-1][x]\n\n if x and y:\n # remove repeated part of top-left pixel\n result -= integral_image[y-1][x-1]\n \n return result\n \n # ----------------------------------------\n # building integral image to speed up block sum computation\n for y in range(0, h):\n for x in range(0, w):\n integral_image[y][x] = update(x, y)\n \n \n \n # compute block sum by looking-up integral image\n output_image = [ [ 0 for y in range(w) ] for x in range(h) ]\n \n for y in range(h):\n for x in range(w):\n \n min_row, max_row = max( 0, y-K), min( h-1, y+K)\n min_col, max_col = max( 0, x-K), min( w-1, x+K)\n \n output_image[y][x] = integral_image[max_row][max_col]\n \n if min_row > 0:\n output_image[y][x] -= integral_image[min_row-1][max_col]\n \n if min_col > 0:\n output_image[y][x] -= integral_image[max_row][min_col-1]\n \n if min_col > 0 and min_row > 0:\n output_image[y][x] += integral_image[min_row-1][min_col-1]\n \n return output_image\n```\n\n

\n\n---\n\n**Implentation** with integral image building in top-down DP \n\n

\n\t

Click to show source code

\n\t\n```\nclass Solution:\n def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n \n h, w = len(mat), len( mat[0])\n integral_image = [ [ 0 for y in range(w) ] for x in range(h) ]\n \n #-----------------------------------------\n def build_integral_image(x, y):\n \n if (x < 0) or (y < 0):\n \n ## base case:\n # zero for those pixels out of valid boundary\n return 0\n \n if integral_image[y][x]:\n ## base case:\n # direcly look-up table\n return integral_image[y][x]\n \n ## general cases\n # comptue and update integral image at (x, y)\n \n integral_image[y][x] = mat[y][x] + build_integral_image(x, y-1) + build_integral_image(x-1, y) - build_integral_image(x-1, y-1)\n \n return integral_image[y][x]\n \n # ----------------------------------------\n # building integral image to speed up block sum computation\n build_integral_image(w-1, h-1)\n \n \n # compute block sum by looking-up integral image\n output_image = [ [ 0 for y in range(w) ] for x in range(h) ]\n \n for y in range(h):\n for x in range(w):\n \n min_row, max_row = max( 0, y-K), min( h-1, y+K)\n min_col, max_col = max( 0, x-K), min( w-1, x+K)\n \n output_image[y][x] = integral_image[max_row][max_col]\n \n if min_row > 0:\n output_image[y][x] -= integral_image[min_row-1][max_col]\n \n if min_col > 0:\n output_image[y][x] -= integral_image[max_row][min_col-1]\n \n if min_col > 0 and min_row > 0:\n output_image[y][x] += integral_image[min_row-1][min_col-1]\n \n return output_image\n```\n\n

\n\n---\n\nRelated leetcode challenge:\n[Leetcode #304 Range Sum Query 2D - Immutable](https://leetcode.com/problems/range-sum-query-2d-immutable/)\n\n[Leetcode #303 Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/)\n\n---\n\nReference:\n[Integral Image in wikipedia](https://en.wikipedia.org/wiki/Summed-area_table)\n\n---\n\nFurther reading:\n[1] [Integral Image in OpenCV API](https://docs.opencv.org/master/d5/de6/group__cudaarithm__reduce.html#ga07e5104eba4bf45212ac9dbc5bf72ba6)\n\n[2] [ImageJ: Integral Image Filter](https://imagej.net/Integral_Image_Filters)\n\n---\n\nThanks for your reading.\n\nWish you have a nice day.\n\nMeow~\uD83D\uDE3A

Matrix Block Sum

Problem Description

Problem Description

Answer Panel