Compute before Matrix

0 0 7 minutes read

For a given matrix before[][], the corresponding cell (x, y) of the after[][] matrix is calculated as follows:

res = 0;
for(i = 0; i <= x; i++){
for( j = 0; j <= y; j++){
res += before(i, j);
}
}
after(x, y) = res;

Given an N*M matrix after[][], your task is to find the corresponding before[][] matrix for the given matrix.

Examples:

Input: N = 2, M = 3, after[][] = { {1, 3, 6}, {3, 7, 11} }
Output:
1 2 3
2 2 1
Explanation: The before matrix for the given after matrix is { {1, 2, 3}, {2, 2, 1} }.
Because according to the code given in problem,
after(0, 0) = before(0, 0) = 1
after(0, 1) = before(0, 0) + before(0, 1) = 1 + 2 = 3.
after(0, 2) = before(0, 0) + before(0, 1) + before(0, 2) = 1 + 2 + 3 = 6.
after(1, 0) = before(0, 0) + before(1, 0) = 1 + 2 = 3;,
after(1, 1) = before(0, 0) + before(0, 1) + before(1, 0) + before(1, 1) = 1 + 2 + 2 + 2 = 7.
after(1, 2) = before(0, 0) + before(0, 1) + before(0, 2) + before(1, 0) + before(1, 1) + before(1, 2) = 1 + 2 + 3 + 2 + 2 + 1 = 11

Input: N = 1, M = 3, after[][] = { {1, 3, 5} }
Output:
1 2 2

Approach: The problem can be solved based on the following observation:

Consider the opposite task, i.e. to convert before[][] matrix to after[][]. As seen from the problem statement, after[i][j] is the summation of all the cells to the left of j^th column and all the rows above the i^th row. That is basically the prefix sum of a matrix.

Based on the above observation the problem can be solved with the help of the example as shown below:

Consider before[][] = { {1, 2, 3}, {2, 2, 1} }

before[][] matrix

See how this matrix is converted into after[][] matrix.

For (0, 0): after[0][0] = before[0][0] = 1
For (0, 1): after[0][1] = before[0][0] + before[0][1] = after[0][0] + before[0][1] = 1 + 2 = 3
For (0, 2): after[0][2] = before[0][0] + before[0][1] + before[0][2] = after[0][1] + before[0][2] = 3 + 3 = 6
For (1, 0): after[1][0] = before[0][0] + before[1][0] = after[0][0] + before[1][0] = 1 + 2 = 3
For (1, 1): after[1][1] = before[0][0] + before[0][1] + before[1][0] + before[1][1] = before[0][0] + before[0][1] + before[0][0] + before[1][0] – before[0][0] + before[1][1] = after[0][1] + after[1][0] – after[0][0] + before[1][1] = 3 + 3 – 1 + 2 = 7
For (1, 2): Similarly like the previous one
after[1][2] = after[0][2] + after[1][1] – after[0][1] + before[1][2] = 6 + 7 – 3 + 1 = 11

Note: In the procedure, if the value of i and j is non-zero then in that case while taking the values from up and left sides of i and j respectively, we have counted twice the value of the after[i-1][j-1].

Now from the above procedure only we are going to determine how to get the before[][] matrix when we have been given after[][] matrix

For the first row:
after[i][j] = after[i][j-1] + before[i][j] can be converted to before[i][j] = after[i][j] – after[i][j-1]

For the first column:
after[i][j] = after[i-1][j] + before[i][j] can be converted to before[i][j] = after[i][j] – after[i-1][j]

For the first cell (i=0, j=0): before[0][0] = after[0][0]
For the rest of the cell:
after[i][j] = after[i-1][j] + after[i][j-1] – after[i-1][j-1] + before[i][j] can be converted to before[i][j] = after[i][j] + after[i-1][j-1] – after[i-1][j] – after[i][j-1]

Follow the steps mentioned below to implement the approach:

Iterate through all the cells (i, j) of the matrix:
- Check the values of (i, j) to determine the location of the cell.
- Based on the location, use one of the formulae shown above and determine the value of before[i][j].
Return the before[][] matrix after the iteration is over.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to compute before matrix
vector<vector<int> >
computeBeforeMatrix(int N, int M,
                    vector<vector<int> >& after)
{
    // Declaring a  2d vector to store
    // the values of the before Matrix
    vector<vector<int> > before(N,
                                vector<int>(M, 0));
    before[0][0] = after[0][0];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (i == 0 && j == 0)
                continue;
            else if (i == 0)
                before[i][j]
                    = after[i][j] - after[i][j - 1];
            else if (j == 0)
                before[i][j]
                    = after[i][j] - after[i - 1][j];
            else
                before[i][j]
                    = after[i][j] + after[i - 1][j - 1]
                      - after[i - 1][j] - after[i][j - 1];
        }
    }
 
    // Return the before[][] matrix
    return before;
}
 
// Driver code
int main()
{
    int N = 2, M = 3;
    vector<vector<int> > after{ { 1, 3, 6 }, { 3, 7, 11 } };
 
    // Function call
    vector<vector<int> > ans
        = computeBeforeMatrix(N, M, after);
    for (auto u : ans) {
        for (int x : u)
            cout << x << " ";
        cout << endl;
    }
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
 
class GFG
{
 
  // Function to compute before matrix
  public static int[][] computeBeforeMatrix(int N, int M,
                                            int after[][])
  {
 
    // Declaring a 2d matrix to store
    // the values of the before Matrix
    int before[][] = new int[N][M];
    before[0][0] = after[0][0];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (i == 0 && j == 0)
          continue;
        else if (i == 0)
          before[i][j]
          = after[i][j] - after[i][j - 1];
        else if (j == 0)
          before[i][j]
          = after[i][j] - after[i - 1][j];
        else
          before[i][j] = after[i][j]
          + after[i - 1][j - 1]
          - after[i - 1][j]
          - after[i][j - 1];
      }
    }
 
    // Return the before[][] matrix
    return before;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 2, M = 3;
    int after[][] = { { 1, 3, 6 }, { 3, 7, 11 } };
 
    // Function call
    int ans[][] = computeBeforeMatrix(N, M, after);
    for (int[] u : ans) {
      for (int x : u)
        System.out.print(x + " ");
      System.out.println();
    }
  }
}
 
// This code is contributed by Rohit Pradhan

Python3

# Python code to implement the approach
 
# Function to compute before matrix
def computeBeforeMatrix(N, M, after):
 
    # Declaring a 2d vector to store
    # the values of the before Matrix
    before = [[0 for i in range(M)]for j in range(N)]
 
    before[0][0] = after[0][0]
    for i in range(N):
        for j in range(M):
            if (i == 0 and j == 0):
                continue
            elif (i == 0):
                before[i][j] = after[i][j] - after[i][j - 1]
            elif (j == 0):
                before[i][j] = after[i][j] - after[i - 1][j]
            else: 
                before[i][j] = after[i][j] + after[i - 1][j - 1] - after[i - 1][j] - after[i][j - 1]
                 
 
            # Return the before[][] matrix
    return before
 
# Driver code
 
N,M = 2,3
after = [[1, 3, 6], [3, 7, 11]]
 
# Function call
ans = computeBeforeMatrix(N, M, after)
for u in ans:
    for x in u:
        print(f"{x}",end=" ")
    print("")
 
 
# This code is contributed by shinjanpatra

C#

using System;
 
public class GFG {
  public static int[, ] computeBeforeMatrix(int N, int M,
                                            int[, ] after)
  {
 
    // Declaring a 2d matrix to store
    // the values of the before Matrix
    int[, ] before = new int[N, M];
    before[0, 0] = after[0, 0];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (i == 0 && j == 0)
          continue;
        else if (i == 0)
          before[i, j]
          = after[i, j] - after[i, j - 1];
        else if (j == 0)
          before[i, j]
          = after[i, j] - after[i - 1, j];
        else
          before[i, j] = after[i, j]
          + after[i - 1, j - 1]
          - after[i - 1, j]
          - after[i, j - 1];
      }
    }
 
    // Return the before[][] matrix
    return before;
  }
  static public void Main()
  {
    int N = 2, M = 3;
    int[, ] after
      = new int[, ] { { 1, 3, 6 }, { 3, 7, 11 } };
 
    // Function call
    int[, ] ans = computeBeforeMatrix(N, M, after);
    for (int i = 0; i < ans.GetLength(0); i++) {
      for (int j = 0; j < ans.GetLength(1); j++)
        Console.Write(ans[i, j] + " ");
      Console.WriteLine();
    }
  }
}
 
// This code is contributed by ishankhandelwals

Javascript

<script>
    // JavaScript code to implement the approach
 
    // Function to compute before matrix
    const computeBeforeMatrix = (N, M, after) => {
     
        // Declaring a 2d vector to store
        // the values of the before Matrix
        let before = new Array(N).fill(0).map(() => new Array(M).fill(0));
 
        before[0][0] = after[0][0];
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (i == 0 && j == 0)
                    continue;
                else if (i == 0)
                    before[i][j]
                        = after[i][j] - after[i][j - 1];
                else if (j == 0)
                    before[i][j]
                        = after[i][j] - after[i - 1][j];
                else
                    before[i][j]
                        = after[i][j] + after[i - 1][j - 1]
                        - after[i - 1][j] - after[i][j - 1];
            }
        }
 
        // Return the before[][] matrix
        return before;
    }
 
    // Driver code
 
    let N = 2, M = 3;
    let after = [[1, 3, 6], [3, 7, 11]];
 
    // Function call
    let ans = computeBeforeMatrix(N, M, after);
    for (let u in ans) {
        for (let x in ans[u])
            document.write(`${ans[u][x]} `);
        document.write("<br/>");
    }
 
// This code is contributed by rakeshsahni
 
</script>

Output

1 2 3 
2 2 1

Time Complexity: O(M * N) where M is the number of rows and N is the number of columns
Auxiliary Space: O(M * N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!