For each cell in the result array, we need to add some of the matrix elements based on the *k value and row and column values*. Easy and simple solution is given below:

This simple solution has a time complexity of *O(m*n*k*k)*

When computing the sums for certain elements in the resulting matrix `res`

, we observe redundancy in the addition of elements. For instance, when calculating `res[0][0]`

, elements `mat[0][0]`

, `mat[0][1]`

, `mat[1][0]`

, and `mat[1][1]`

are added. Then, when computing `res[0][1]`

, these same elements are added again along with `mat[0][2]`

and `mat[1][2]`

, resulting in redundant computations. By trying to avoid these redundant computations, we can reduce time complexity.

**Prefix sum**

We can optimize the solution using the concept of prefix sum. Prefix sum is a technique used to compute the sum of elements in a sequence.

For a 1D array, we initialize `prefix_sum[0]`

to 0, and then compute subsequent elements as `prefix_sum[i] = prefix_sum[i-1] + mat[i-1]`

. This allows us to quickly calculate the sum of elements within a specified range from `i-k`

to `i+k`

using `prefix_sum[i+k+1] - prefix_sum[i-k+1]`

.

Similarly, we can extend this concept to a 2D array to reduce the time complexity of the solution. By precomputing prefix sums along rows and columns, we can efficiently compute the sum of elements within a specified range for each cell in the resulting matrix.

Here is the solution:

This solution uses the prefix sum and dynamic programming concepts to reduce the time complexity.