A speed up I can suggest: pre-compute another grid, say sumGrid where sumGrid[x][y] = sum(grid[i][j] where i is in range(x, N) and j in range(y, N)
sumGrid[x][y] = sum(grid[i][j]
So, each element in this new sumGrid is the sum of all elements below and right to it, including itself.
Then sum(x,y,size) is now just:
As an example, sum(3,2,5) would look like this:
We need to add that 4th last term sumGrid[x+size][y+size] since we have subtracted it twice as part of terms 2 and 3. The solution now avoids two inner for loops — making it much faster :)
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.