Wednesday, 27 Oct 2021

# Generate a matrix having each element equal to the sum of specified submatrices of a given matrix

Generate a matrix having each element equal to the sum of specified submatrices of a given matrix
Given a matrix mat[][] of dimensions M*N and an integer K, the task is to generate a matrix answer[][], where answer[i][j] is equal to the sum of all elements mat[r] such that r ∈ [i – K, i + K], c ∈ [j – K, j + K], and (r, c) is a valid position in the matrix.
Examples:

Input: mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, K = 1Output: {{12, 21, 16}, {27, 45, 33}, {24, 39, 28}}Explanation:answer = mat + mat + mat + mat =1 + 2 + 4 + 5 = 12.answer = mat + mat + mat + mat + mat + mat = 1 + 2 + 3 + 4 + 5 + 6 = 21.Similarly, answer = 16, answer = 27, answer = 45, answer = 33, answer = 24, answer = 39, answer = 28
Input: mat = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, K = 2Output: {{45, 45, 45}, {45, 45, 45}, {45, 45, 45}}

Naive Approach: The simplest approach is to iterate over the matrix elements using two nested loops and calculate the sum of all the elements mat[r] ( i – K ≤ r ≤ i + K, j – K ≤ c ≤ j+K ), for every possible answer[i][j]. Finally, print the matrix after traversing the matrix.Time Complexity: O(N4) Auxiliary Space: O(1)
Prefix Sum based Approach: To optimize the above approach, the idea is to initialize an auxiliary matrix aux[M][N] to store the prefix sum of all the rows of the matrix mat[][]. Once aux[][] is constructed, answer[i][j] can be calculated by traversing all rows in the range [i – K ≤ r ≤ i + K] and adding aux[r][max_col] – aux[r][min_col] + aux[r][min_col] to it. This value added denotes the sum contributed by row[r] to answer[i][j].
Below is the implementation of the above approach:
Python3

def matrixBlockSum(mat, K):

n = len(mat)
m = len(mat)

for i in range(n):
k = 0
for j in range(m):

k += mat[i][j]
mat[i][j] = (mat[i][j], k)

ans = []

for i in range(n):

temp = []
for j in range(m):

mnr = max(0, i – K)
mnc = max(0, j – K)
mxr = min(n – 1, i + K)
mxc = min(m – 1, j + K)
ans1 = 0

for k in range(mnr, mxr+1):
ans1 += (mat[k][mxc]-mat[k][mnc])+mat[k][mnc]

temp.append(ans1)

ans.append(temp)

print(ans)

if __name__ == “__main__”:

mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
K = 1
matrixBlockSum(mat, K)

Output:

[[12, 21, 16], [27, 45, 33], [24, 39, 28]]

Time Complexity: O(N3) Auxiliary Space: O(N2)
Efficient Approach: To optimize the above approach, the idea is to initialize an auxiliary matrix aux[M][N] such that aux[i][j] stores the sum of elements in the submatrix mat to mat[i][j] using the following expression:

Sum of the submatrix between indices (mnr, mnc) and (mxr, mxc) is given by:  aux[mxr][mxc] – aux[mnr – 1][mxc] – aux[mxr][mnc – 1] + aux[mnr – 1][mnc – 1]
Note: The submatrix aux[mnr-1][mnc-1] is added because elements of it are subtracted twice.

Follow the steps below to construct the aux matrix:
Copy first row of mat[][] to aux[][].
Find column-wise sum of the matrix and store it.
Find the row-wise sum of updated matrix aux[][].
After the above steps, print the matrix aux[][] generated.
Below is the implementation of the above approach:

Python3

def matrixBlockSum(mat, K):

n = len(mat)
m = len(mat)

for i in range(n):

for j in range(m):

if i-1 >= 0:
mat[i][j] += mat[i-1][j]
if j-1 >= 0:
mat[i][j] += mat[i][j-1]
if i-1 >= 0 and j-1 >= 0:
mat[i][j] -= mat[i-1][j-1]

ans = [[0 for i in range(m)]for i in range(n)]

for i in range(n):
for j in range(m):

mnr = max(0, i – K)
mxr = min(i + K, n-1)
mnc = max(0, j – K)
mxc = min(j + K, m-1)

ans[i][j] = mat[mxr][mxc]

if mnr – 1 >= 0:
ans[i][j] -= mat[mnr-1][mxc]

if mnc – 1 >= 0:
ans[i][j] -= mat[mxr][mnc-1]

if mnr – 1 >= 0 and mnc – 1 >= 0:
ans[i][j] += mat[mnr – 1][mnc – 1]

print(ans)

if __name__ == “__main__”:

mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

K = 1

matrixBlockSum(mat, K)

Output:

[[12, 21, 16], [27, 45, 33], [24, 39, 28]]

Time Complexity: O(N2)Auxiliary Space: O(N2)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.