Integral Image Build

Problem

Build a summed-area table (integral image).

Return a (H + 1) x (W + 1) grid whose first row and column are zeros, where s[i + 1][j + 1] is the sum of the input rectangle from (0, 0) to (i, j) inclusive.

Hint

Each cell is the input value plus the cell above plus the cell left minus the diagonal.

Test cases

case 1

in: [[[1,2],[3,4]]]

expected: [[0,0,0],[0,1,3],[0,4,10]]

case 2

in: [[[1,2,3]]]

expected: [[0,0,0,0],[0,1,3,6]]

case 3

in: [[[5]]]

expected: [[0,0],[0,5]]

case 4

in: [[[-1,2],[3,-4]]]

expected: [[0,0,0],[0,-1,1],[0,2,0]]

Starter codePython

def integral_image(image):
    # Your code here
    pass

4 test cases · run your code against them in the editor