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 = 11Input: 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 jth column and all the rows above the ith 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 matrixvector<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 codeint 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 approachimport 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 matrixdef 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 codeN,M = 2,3after = [[1, 3, 6], [3, 7, 11]]# Function callans = 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> |
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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
