Compute Every Fixed-Size Submatrix Sum

Problem

Given an integer matrix and an integer k, compute the sum of every contiguous k x k submatrix. Return a matrix where output cell [r][c] is the sum of the submatrix whose top-left corner is input cell [r][c].

Function Contract

Implement k_by_k_sums(matrix, k) -> list[list[int]]. Do not mutate the input.

Constraints

• 1 <= rows, columns <= 1000 and the total cell count is at most 10^6.
• 1 <= k <= min(rows, columns).
• Values lie in [-10^9, 10^9].
• The output shape is (rows-k+1) x (columns-k+1).

Examples

• For [[1,2,3],[4,5,6],[7,8,9]] and k = 2, return [[12,16],[24,28]].
• When k = 1, return a copy of the input matrix.

Edge Cases

• Negative values can make a submatrix sum negative.
• When k equals both dimensions, the output has one cell.
• Sums can exceed 32-bit range.