Compute Matrix before Given Operations

There are two matrices, before[][] and after[][] of size N×M. The matrix after[][] is obtained by applying the 2D prefix sum operation on before[][]. Given the matrix after[][], reconstruct the original matrix before[][].

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] - Reconstruct the Matrix from 2D Prefix Sum O(n × m ) time and O(n × m ) space

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.  So this problem is mainly an extension of Original Array from given Prefix Sums

• Using the 2D prefix sum formula: prefix[i][j] = arr[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
• Rearranging the equation, we get: arr[i][j] = prefix[i][j] - prefix[i-1][j] - prefix[i][j-1] + prefix[i-1][j-1]

//Driver Code Starts
#include<iostream>
#include<vector>
using namespace std;

//Driver Code Ends

vector<vector<int>> computeBeforeMatrix(vector<vector<int>>& after) {
    int n = after.size(), m = after[0].size();
    
    // Declaring a 2d array to store
    // the values of the before Matrix
    vector<vector<int>> before(n, vector<int>(m, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0)
                before[0][0] = after[0][0];
            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 before;
}

//Driver Code Starts

int main() {
    vector<vector<int>> after{ {1, 3, 6 }, { 3, 7, 11 } };

    vector<vector<int>> ans = computeBeforeMatrix(after);
    for (auto u : ans) {
        for (int x : u)
            cout << x << " ";
        cout << endl;
    }
    return 0;
}
//Driver Code Ends

class GfG {

    static int[][] computeBeforeMatrix(int[][] after) {
        int n = after.length, m = after[0].length;
        
        // Declaring a 2D array to store
        // the values of the before Matrix
        int[][] before = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0)
                    before[0][0] = after[0][0];
                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 before;
}


//Driver Code Starts
    public static void main(String[] args) {
        int[][] after = { { 1, 3, 6 }, { 3, 7, 11 } };

        int[][] ans = computeBeforeMatrix(after);
        for (int[] row : ans) {
            for (int x : row)
                System.out.print(x + " ");
            System.out.println();
        }
    }
}

//Driver Code Ends

def computeBeforeMatrix(after):
    n, m = len(after), len(after[0])
    
    # Declaring a 2D list to store
    # the values of the before Matrix
    before = [[0] * m for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                before[0][0] = after[0][0]
            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 before

if __name__ == "__main__":
    after = [[1, 3, 6], [3, 7, 11]]

    ans = computeBeforeMatrix(after)
    for row in ans:
        print(" ".join(map(str, row)))

//Driver Code Starts
using System;
using System.Collections.Generic;

//Driver Code Ends

class GfG {
    static List<List<int>> computeBeforeMatrix(List<List<int>> after) {
        int n = after.Count, m = after[0].Count;
        
        // Declaring a 2D list to store
        // the values of the before Matrix
        List<List<int>> before = new List<List<int>>();
        for (int i = 0; i < n; i++) 
            before.Add(new List<int>(new int[m]));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j == 0)
                    before[0][0] = after[0][0];
                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 before;
}

//Driver Code Starts

    static void Main() {
        List<List<int>> after = new List<List<int>> {
            new List<int> { 1, 3, 6 },
            new List<int> { 3, 7, 11 }
        };

        List<List<int>> ans = computeBeforeMatrix(after);
        foreach (List<int> row in ans) {
            Console.WriteLine(string.Join(" ", row));
        }
    }
}

//Driver Code Ends

function computeBeforeMatrix(after) {
    let n = after.length, m = after[0].length;
    
    // Declaring a 2D array to store
    // the values of the before Matrix
    let before = Array.from({ length: n }, () => Array(m).fill(0));
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (i === 0 && j === 0)
                before[0][0] = after[0][0];
            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 before;
}

let after = [[1, 3, 6], [3, 7, 11]];

let ans = computeBeforeMatrix(after);
ans.forEach(row => console.log(row.join(" ")));

1 2 3 
2 2 1