Compute Every Fixed-Size Submatrix Sum
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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.
```hint Use a padded 2D prefix sum
A prefix grid with one extra top row and left column lets one rectangle sum use four lookups without boundary branches.
```
### 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.
Overview: Compute every contiguous fixed-size submatrix sum without mutating the input, using a padded two-dimensional prefix grid to answer each window in constant time.
Read the full Citadel Software Engineer interview experience this question came from
Given a nonempty rectangular integer matrix and an integer k, return a matrix in which output[r][c] is the sum of the contiguous k x k submatrix whose top-left cell is matrix[r][c]. Do not mutate the input. The output has shape (rows - k + 1) x (columns - k + 1).
Constraints
- 1 <= rows, columns <= 1000, and rows * columns <= 1000000.
- 1 <= k <= min(rows, columns).
- Every matrix value lies in [-1000000000, 1000000000].
- The output shape is (rows - k + 1) x (columns - k + 1).
- Submatrix sums may exceed 32-bit range.
Examples
Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 2)
Expected Output: [[12, 16], [24, 28]]
Explanation: This is the source example with four overlapping two-by-two submatrices.
Input: ([[1, -2, 3], [4, 5, -6]], 1)
Expected Output: [[1, -2, 3], [4, 5, -6]]
Explanation: When k is one, each output cell copies the corresponding input value.
Hints
- Use a prefix grid with one extra zero row and column so each rectangle sum needs four lookups.