Mado Sum: Sliding Window Sum Across a 2D Matrix with Variable Window Size

Problem "Mado" means window in Japanese. Given an m x n integer matrix and a window size k, compute the sum of every valid k x k submatrix. Return all sums in a result matrix of size (m-k+1) x (n-k+1). Optimize beyond the naive O(m n k^2) approach. Follow-ups Describe the 2D prefix sum technique. What is its time and space complexity? How does your approach handle matrices where k > min(m, n)? What if instead of sum you need the maximum value in each window? How does your approach change? Extend…