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.
