Matrix Summation Hackerrank Solution

The below algorithm is used to transform the matrix and we will use it for Matrix Summation. We need to find the original matrix, given the transformed matrix.

The algorithm used for the transformation

v = 0
for i in range(x+1):
   for j in range(y+1):
      v += before(i,j)
after(x,y) = v

This algorithm will run for every x and y in the original matrix.

Example

Algorithm for Matrix Summation Hackerrank Solution

before(0,0) => before(0,0)
before(0,1) => before(0,0) + before(0,1)
before(1,0) => before(0,0) + before(1,0)
before(1,1) => before(0,0) + before(0,1) + before(1,0) + before(1,1)

In, this way the matrix is transformed.

Our task is to write a function, that takes the transformed matrix as input and returns the original matrix. This can also be termed as decoding a matrix.

Approach

The transforming algorithm adds all the previous elements of that row and column. To get back to the original matrix, we need to subtract from previous values and add the previous diagonal values. We just need to take care of the appropriate boundary conditions.

Algorithm

for(i=x-1; i<=0; i--){
   for(j=y-1; j<=0; j--){
      if(i-1 >= 0 && j-1 >= 0){
         transfromedMatrix[i][j] = transfromedMatrix[i][j] - transfromedMatrix[i-1][j] - transfromedMatrix[i][j-1] + transfromedMatrix[i-1][j-1]
      }
      else if(j-1 >= 0){
         transfromedMatrix[i][j] -= transfromedMatrix[i][j-1]
      }
      else if(i-1 >= 0){
         transfromedMatrix[i][j] -= transfromedMatrix[i-1][j]
      }

Python Solution for Matrix Summation Hackerrank Solution

def getOriginalMatrix(transformedMatrix):
    x = len(transformedMatrix)
    y = len(transformedMatrix[0])
    
    for i in range(x-1, -1, -1):
        for j in range(y-1, -1, -1):
            if i-1 >= 0 and j-1 >= 0:
                transformedMatrix[i][j] = transformedMatrix[i][j] - transformedMatrix[i-1][j] - transformedMatrix[i][j-1] + transformedMatrix[i-1][j-1]
            elif j-1 >= 0:
                transformedMatrix[i][j] -= transformedMatrix[i][j-1]
            elif i-1 >= 0:
                transformedMatrix[i][j] -= transformedMatrix[i-1][j]
    
    return transformedMatrix

Also Read:

Share:
Avatar of Mohsin Shaikh

Author: Mohsin Shaikh