How should I practice Centered K-by-K Submatrix Sums?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Citadel onsite interview problems in FastPrep.

Is Centered K-by-K Submatrix Sums associated with Citadel?

FastPrep tags this as a Citadel onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Matrix

Centered K-by-K Submatrix Sums

Learn this problem

● Medium

CitadelINTERNONSITE INTERVIEW

Problem statement

You are given a non-empty integer matrix matrix and a positive odd integer k. Construct an output matrix with the same dimensions.

Let radius = (k - 1) / 2. For every cell (row, col), sum all input cells inside the centered k-by-k window:

row - radius <= i <= row + radius
col - radius <= j <= col + radius

Clip the window to valid matrix coordinates. Return the per-cell sums using signed 64-bit integers.

Function

centeredSubmatrixSums(matrix: int[][], k: int) → long[][]

Examples

Example 1

matrix = [[1,2,3],[4,5,6],[7,8,9]]k = 3return = [[12,21,16],[27,45,33],[24,39,28]]

The center cell sees the whole matrix and has sum 45. The top-left cell sees only [[1,2],[4,5]], whose sum is 12.

Example 2

matrix = [[2,-1,4],[0,3,5]]k = 1return = [[2,-1,4],[0,3,5]]

When k = 1, each centered window contains only its own cell.

Example 3

matrix = [[1,2,3],[4,5,6]]k = 5return = [[21,21,21],[21,21,21]]

The radius is 2, so after clipping, every window covers the complete matrix and has sum 21.

Constraints

1 <= matrix.length, matrix[0].length <= 1000.
k is positive and odd.
1 <= k <= 2 * max(matrix.length, matrix[0].length) + 1.
-10^9 <= matrix[row][col] <= 10^9.
Every output sum fits in a signed 64-bit integer.