For a given 2D 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 2D-Matrix after, your task is to find the corresponding before matrix for the given matrix.
 
Example 1:
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
matrix is {{1, 2, 3}, {2, 2, 1}}.
Reason:
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.
Similarly we can calculate values for every
cell of the after matrix.
 
Example 2:
Input: 
N = 1, M = 3
after[][] = {{1, 3, 5}}
Output:
1 2 2
Explanation: 
The before matrix for the given after matrix
is {{1, 2, 2}}.
Your Task:
Complete the function computeBeforeMatrix() which takes the integers N, M, and the 2D Matrix after as the input parameters, and returns the before matrix of the given after matrix.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, M, after[i][j]  ≤  10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Range queries

Starter code: #User function Template for python3



class Solution:

    def computeBeforeMatrix(self, N, M, after):

        # Code here



Solutions:
class Solution:

	def computeBeforeMatrix(self, N, M, after):
		ans = [[0 for _ in range(M)] for _ in range(N)]
		ans[0][0] = after[0][0]
		for i in range(1, M):
			ans[0][i] = after[0][i] - after[0][i - 1]
		for i in range(1, N):
			ans[i][0] = after[i][0] - after[i - 1][0]
		for i in range(1, N):
			for j in range(1, M):
				ans[i][j] = after[i][j] - after[i - 1][j] - after[i][j - 1] + after[i - 1][j - 1]
		return ans


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		before = [[0 for j in range(M)] for i in range(N)]
		for i in range(N):
			for j in range(M):
				if i == 0:
					if j > 0:
						before[i][j] = after[i][j] - after[i][j - 1]
					else:
						before[i][j] = after[i][j]
				elif i > 0:
					if j == 0:
						before[i][j] = after[i][j] - after[i - 1][j]
					else:
						before[i][j] = after[i][j] - (after[i][j - 1] - after[i - 1][j - 1] + after[i - 1][j])
		return before


class Solution:

	def computeBeforeMatrix(self, n, m, after):
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if i == 0 and j == 0:
					continue
				elif i == 0 and j > 0:
					after[i][j] -= after[i][j - 1]
				elif j == 0 and i > 0:
					after[i][j] -= after[i - 1][j]
				else:
					after[i][j] -= after[i - 1][j] + after[i][j - 1] - after[i - 1][j - 1]
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		before = [[0 for i in range(M)] for j in range(N)]
		for i in range(N):
			for j in range(M):
				a = after[i][j]
				b1 = after[i - 1][j] if i - 1 >= 0 else 0
				b2 = after[i][j - 1] if j - 1 >= 0 else 0
				b3 = after[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0
				before[i][j] = a - b1 - b2 + b3
		return before


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		prefix = [[0] * M for i in range(N)]
		before = [[0] * M for i in range(N)]
		prefix[0][0] = after[0][0]
		before[0][0] = after[0][0]
		for i in range(1, N):
			before[i][0] = after[i][0] - prefix[i - 1][0]
			prefix[i][0] = before[i][0] + prefix[i - 1][0]
		for j in range(1, M):
			before[0][j] = after[0][j] - prefix[0][j - 1]
			prefix[0][j] = before[0][j] + prefix[0][j - 1]
		for i in range(1, N):
			for j in range(1, M):
				before[i][j] = after[i][j] - (prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1])
				prefix[i][j] = before[i][j] + (prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1])
		return before


class Solution:

	def computeBeforeMatrix(self, N, M, arr):
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if i > 0:
					arr[i][j] -= arr[i - 1][j]
				if j > 0:
					arr[i][j] -= arr[i][j - 1]
				if i > 0 and j > 0:
					arr[i][j] += arr[i - 1][j - 1]
		return arr


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		a = [[0 for i in range(M)] for i in range(N)]
		sum = 0
		for i in range(M):
			a[0][i] = after[0][i] - sum
			sum += a[0][i]
		for i in range(1, N):
			sum = 0
			for j in range(M):
				a[i][j] = after[i][j] - after[i - 1][j] - sum
				sum += a[i][j]
		return a


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		res = [[0 for i in range(M)] for i in range(N)]
		res[0][0] = after[0][0]
		for i in range(1, N):
			res[i][0] = after[i][0] - after[i - 1][0]
		for i in range(1, M):
			res[0][i] = after[0][i] - after[0][i - 1]
		for i in range(1, N):
			for j in range(1, M):
				res[i][j] = after[i][j] + after[i - 1][j - 1] - after[i - 1][j] - after[i][j - 1]
		return res


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		for r in range(N - 1, 0, -1):
			for c in range(M):
				after[r][c] -= after[r - 1][c]
		for c in range(M - 1, 0, -1):
			for r in range(N):
				after[r][c] -= after[r][c - 1]
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		res = [[0] * M for _ in range(N)]
		for r in range(N):
			for c in range(M):
				prevcells = after[r - 1][c] if r > 0 else 0
				tmp = after[r - 1][c - 1] if r > 0 and c > 0 else 0
				prevcols = after[r][c - 1] - tmp if c > 0 else 0
				res[r][c] = after[r][c] - prevcells - prevcols
		return res


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		pre = 0
		upR = [0] * M
		for i in range(N):
			for j in range(M):
				if i == 0 and j == 0:
					pre = after[i][j]
					continue
				up = upR[j]
				if j == 0:
					pre = 0
				x = after[i][j]
				after[i][j] = after[i][j] - pre - up
				pre = x
				if j == M - 1:
					pre = 0
			upR = [upR[k] + after[i][k] for k in range(M)]
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		arr = []
		for i in range(N):
			arr.append([0 for j in range(M)])
		arr[0][0] = after[0][0]
		for x in range(1, M):
			arr[0][x] = after[0][x] - after[0][x - 1]
		for y in range(1, N):
			arr[y][0] = after[y][0] - after[y - 1][0]
		for j in range(1, N):
			for k in range(1, M):
				arr[j][k] = after[j][k] - after[j - 1][k] - after[j][k - 1] + after[j - 1][k - 1]
		return arr


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		for i in range(N):
			after[i].insert(0, 0)
		after.insert(0, [0] * (M + 1))
		for i in range(N, 0, -1):
			for j in range(M, 0, -1):
				after[i][j] -= after[i - 1][j] + after[i][j - 1] - after[i - 1][j - 1]
		return [[after[i][j] for j in range(1, M + 1)] for i in range(1, N + 1)]
if __name__ == '__main__':
	T = int(input())
	while T > 0:
		(N, M) = [int(i) for i in input().split()]
		after = []
		for j in range(N):
			after.append([int(i) for i in input().split()])
		ob = Solution()
		before = ob.computeBeforeMatrix(N, M, after)
		for i in range(len(before)):
			for j in range(len(before[i])):
				print(before[i][j], end=' ')
			print()
		T -= 1


class Solution:

	def computeBeforeMatrix(self, N, M, matrix):
		n = len(matrix)
		m = len(matrix[0])
		before = [[0 for i in range(m)] for j in range(n)]
		before[0][0] = matrix[0][0]
		for i in range(n):
			for j in range(m):
				if i == 0 and j > 0:
					before[i][j] = matrix[i][j] - matrix[i][j - 1]
				elif j == 0 and i > 0:
					before[i][j] = matrix[i][j] - matrix[i - 1][j]
				elif j > 0 and i > 0:
					before[i][j] = matrix[i][j] - (matrix[i][j - 1] + matrix[i - 1][j] - matrix[i - 1][j - 1])
		return before
if __name__ == '__main__':
	T = int(input())
	while T > 0:
		(N, M) = [int(i) for i in input().split()]
		after = []
		for j in range(N):
			after.append([int(i) for i in input().split()])
		ob = Solution()
		before = ob.computeBeforeMatrix(N, M, after)
		for i in range(len(before)):
			for j in range(len(before[i])):
				print(before[i][j], end=' ')
			print()
		T -= 1


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		l = []
		for i in range(len(after)):
			l1 = []
			for j in range(len(after[0])):
				(m, n, t) = (0, 0, 0)
				if j - 1 >= 0:
					m = after[i][j - 1]
				if i - 1 >= 0:
					n = after[i - 1][j]
				if i - 1 >= 0 and j - 1 >= 0:
					t = after[i - 1][j - 1]
				l1.append(after[i][j] - m - n + t)
			l.append(l1)
		return l


class Solution:

	def computeBeforeMatrix(self, N, M, a):
		b = [[0 for i in range(M)] for j in range(N)]
		for i in range(N):
			um = 0
			for j in range(M):
				if i == 0:
					b[i][j] = a[i][j] - um
					um = um + b[i][j]
				if i > 0:
					b[i][j] = a[i][j] - a[i - 1][j] - um
					um = um + b[i][j]
		return b


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		for j in range(M - 1, -1, -1):
			for i in range(N - 1, -1, -1):
				if i - 1 < 0:
					val1 = 0
				else:
					val1 = after[i - 1][j]
				if j - 1 < 0:
					val2 = 0
				else:
					val2 = after[i][j - 1]
				if i - 1 < 0 or j - 1 < 0:
					val3 = 0
				else:
					val3 = after[i - 1][j - 1]
				after[i][j] = after[i][j] - (val1 + val2) + val3
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		i = 0
		j = 0
		before = []
		for _ in range(N):
			before.append([0] * M)
		while i < N:
			j = 0
			while j < M:
				if i == 0 and j == 0:
					before[i][j] = after[i][j]
				elif i == 0 and j != 0:
					before[i][j] = after[i][j] - after[i][j - 1]
				elif i != 0 and 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]
				j += 1
			i += 1
		return before


class Solution:

	def ans(self, x, y, after, before):
		res = after[x][y]
		for i in range(x + 1):
			for j in range(y + 1):
				if i == x and j == y:
					pass
				else:
					res -= before[i][j]
		return res

	def computeBeforeMatrix(self, N, M, after):
		before = [[0 for i in range(M)] for j in range(N)]
		before[0][0] = after[0][0]
		for i in range(1, N):
			before[i][0] = after[i][0] - after[i - 1][0]
		for j in range(1, M):
			before[0][j] = after[0][j] - after[0][j - 1]
		for i in range(1, N):
			for j in range(1, M):
				before[i][j] = after[i][j] + after[i - 1][j - 1] - after[i - 1][j] - after[i][j - 1]
		return before


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		before = [[0 for _ in range(M)] for _ in range(N)]
		for i in range(N):
			l = 0
			for j in range(M):
				if i > 0:
					u = after[i - 1][j]
				else:
					u = 0
				before[i][j] = after[i][j] - l - u
				l += before[i][j]
		return before


class Solution:

	def computeBeforeMatrix(self, n, m, after):
		aux = [[0 for _ in range(m)] for _ in range(n)]
		before = [[0 for _ in range(m)] for _ in range(n)]
		for i in range(n):
			for j in range(m):
				aux[i][j] += aux[i][j - 1] if j > 0 else 0
				before[i][j] = after[i][j] - aux[i][j] - (aux[i - 1][j] if i > 0 else 0)
				aux[i][j] += before[i][j]
			if i > 0:
				aux[i] = [aux[i][j] + aux[i - 1][j] for j in range(m)]
		return before


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		ans = [[0] * M for _ in range(N)]
		for row in range(N):
			curr_row = 0
			for col in range(M):
				if row == 0:
					if col > 0:
						ans[row][col] = after[row][col] - after[row][col - 1]
					else:
						ans[row][col] = after[row][col]
				else:
					if col == 0:
						ans[row][col] = after[row][col] - after[row - 1][col]
					else:
						ans[row][col] = after[row][col] - (curr_row + after[row - 1][col])
					curr_row += ans[row][col]
		return ans


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		for i in range(N - 1, -1, -1):
			for j in range(M - 1, -1, -1):
				if i:
					after[i][j] -= after[i - 1][j]
				if j:
					after[i][j] -= after[i][j - 1]
				if i and j:
					after[i][j] += after[i - 1][j - 1]
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, a):
		l = [[i for i in range(M)] for j in range(N)]
		for i in range(N):
			for j in range(M):
				if i == 0 and j == 0:
					l[i][j] = a[i][j]
				elif i == 0 and j != 0:
					l[i][j] = a[i][j] - a[i][j - 1]
				elif i != 0 and j == 0:
					l[i][j] = a[i][j] - a[i - 1][j]
				else:
					l[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]
		return l


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		before = [[0 for i in range(M)] for j in range(N)]
		res = after[0][0]
		pro = 0
		before[0][0] = res
		h = {}
		for i in range(N):
			for j in range(M):
				if i == 0 and j == 0:
					continue
				elif i == 0 and j > 0:
					before[i][j] = after[i][j] - after[i][j - 1]
				elif j == 0 and i > 0:
					before[i][j] = after[i][j] - after[i - 1][j]
				else:
					if j not in h.keys():
						h[j] = before[i - 1][j]
					else:
						h[j] += before[i - 1][j]
					before[i][j] = after[i][j] - after[i][j - 1]
					before[i][j] -= h[j]
		return before


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		sum = after[0][0]
		after.append([0 for i in range(M)])
		befor = [[0 for i in range(M)] for j in range(N + 1)]
		befor[0][0] = after[0][0]
		for i in range(N + 1):
			for j in range(M):
				if i == 0 and j == 0:
					continue
				elif j == 0:
					befor[i][j] = after[i][j] - after[i - 1][j]
				else:
					befor[i][j] = after[i][j] - after[i - 1][j] - (after[i][j - 1] - after[i - 1][j - 1])
		return befor[:-1][:]


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		for j in range(M - 1, -1, -1):
			for i in range(N - 1, -1, -1):
				if i - 1 < 0:
					v1 = 0
				else:
					v1 = after[i - 1][j]
				if j - 1 < 0:
					v2 = 0
				else:
					v2 = after[i][j - 1]
				if i - 1 < 0 or j - 1 < 0:
					v3 = 0
				else:
					v3 = after[i - 1][j - 1]
				after[i][j] = after[i][j] - v1 - v2 + v3
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		(n, m) = (len(after), len(after[0]))
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				if i - 1 >= 0 and j - 1 >= 0:
					after[i][j] = after[i][j] - (after[i - 1][j] + after[i][j - 1] - after[i - 1][j - 1])
				elif i - 1 >= 0:
					after[i][j] = after[i][j] - after[i - 1][j]
				elif j - 1 >= 0:
					after[i][j] = after[i][j] - after[i][j - 1]
		return after


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		arr = []
		for i in range(N):
			arr.append([0] * M)
		for i in range(0, N):
			for j in range(0, M):
				if i == 0 and j == 0:
					arr[0][0] = after[0][0]
				elif j == 0:
					arr[i][j] = after[i][j] - after[i - 1][j]
				elif i == 0:
					arr[0][j] = after[0][j] - after[0][j - 1]
				else:
					arr[i][j] = after[i][j] - after[i - 1][j] - after[i][j - 1] + after[i - 1][j - 1]
		return arr


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		before = [[0 for _ in range(M)] for _ in range(N)]
		for i in range(N):
			for j in range(M):
				if j == 0:
					prevCol = 0
				else:
					prevCol = after[i][j - 1]
				if i == 0:
					prevRow = 0
				else:
					prevRow = after[i - 1][j]
				if i == 0 or j == 0:
					before[i][j] = after[i][j] - prevCol - prevRow
				else:
					before[i][j] = after[i][j] - prevCol - prevRow + after[i - 1][j - 1]
		return before


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		ans = [[0 for _ in range(M)] for l in range(N)]
		res = 0
		i = N - 1
		j = M - 1
		while i >= 0:
			j = M - 1
			while j >= 0:
				res = 0
				if i - 1 >= 0:
					res += after[i - 1][j]
				if j - 1 >= 0:
					res += after[i][j - 1]
				if i - 1 >= 0 and j - 1 >= 0:
					res -= after[i - 1][j - 1]
				ans[i][j] = after[i][j] - res
				j -= 1
			i -= 1
		return ans


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		new_lst = after
		new_lst.reverse()
		string = ''
		res = []
		for i in range(N):
			temp = []
			for j in range(M):
				try:
					temp.append(new_lst[i][j] - new_lst[i + 1][j])
				except:
					temp.append(new_lst[i][j])
			res.append(temp)
			temp.reverse()
		result = []
		for item in res:
			res1 = []
			for x in range(len(item)):
				try:
					res1.append(item[x] - item[x + 1])
				except:
					res1.append(item[x])
			res1.reverse()
			result.append(res1)
		result.reverse()
		return result


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		res = []
		for i in range(N):
			a = [0] * M
			res.append(a)
		res[0][0] = after[0][0]
		for i in range(N):
			for j in range(M):
				if i == 0 and j != 0:
					res[i][j] = after[i][j] - after[i][j - 1]
				if i != 0 and j == 0:
					res[i][j] = after[i][j] - after[i - 1][j]
				if i > 0 and j > 0:
					res[i][j] = after[i][j] - after[i - 1][j] - after[i][j - 1] + after[i - 1][j - 1]
		return res


class Solution:

	def computeBeforeMatrix(self, N, M, after):
		res = []
		for i in range(N):
			col = []
			for j in range(M):
				if i == 0:
					if j == 0:
						col.append(after[i][j])
					else:
						col.append(after[i][j] - after[i][j - 1])
				elif j == 0:
					col.append(after[i][j] - after[i - 1][j])
				else:
					col.append(after[i][j] - (after[i][j - 1] + after[i - 1][j]) + after[i - 1][j - 1])
			res.append(col)
		return res