You are given a matrix of dimension n*n. All the cells are initially, zero. You are given Q queries, which contains 4 integers a b c d where (a,b) is the TOP LEFT cell and (c,d) is the Bottom Right cell of a submatrix. Now, all the cells of this submatrix have to be incremented by one. After all the Q queries have been performed. Your task is to find the final resulting Matrix.
Note : Zero-Based Indexing is used for cells of the matrix. 
 
Example 1:
Input: n = 6, q = 6,
Queries = {
{4,0,5,3},
{0,0,3,4},
{1,2,1,2},
{1,1,2,3},
{0,0,3,1},
{1,0,2,4}}.
Output: 
2 2 1 1 1 0
3 4 4 3 2 0 
3 4 3 3 2 0
2 2 1 1 1 0
1 1 1 1 0 0
1 1 1 1 0 0
Explanation:After incrementing all the
sub-matrices of given queries we will 
get the final output.
 
 
Example 2:
Input: n = 4, q = 2,
Queries = {
{0,0,3,3},
{0,0,2,2}}.
Output: 
2 2 2 1 
2 2 2 1  
2 2 2 1 
1 1 1 1 
Explanation:After incrementing all the
sub-matrices of given queries we will
get the final output.
Your Task:
You don't need to read or print anything. Your task is to complete the function solveQueries() which takes n and Queries and input parameter and returns a matrix after performing all the queries.
 
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n^{2})
 
Constraints:
1 <= n <= 1000
0 <= a <= c < n
0 <= b <= d < n
1 <= No. of Queries <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

	def solveQueries(self, n, Queries):

		# Code here

Solutions:
from itertools import accumulate

class Solution:

	def solveQueries(self, n, Queries):
		temp = [[0] * n for _ in range(n)]
		for (a, b, c, d) in Queries:
			for i in range(a, c + 1):
				temp[i][b] += 1
			if d < n - 1:
				for i in range(a, c + 1):
					temp[i][d + 1] -= 1
		for i in range(n):
			temp[i] = list(accumulate(temp[i]))
		return temp


class Solution:

	def solveQueries(self, n, Queries):
		ans = [[0] * n for _ in range(n)]
		for [up, left, down, right] in Queries:
			ans[up][left] += 1
			if right + 1 < n:
				ans[up][right + 1] -= 1
			if down + 1 < n:
				ans[down + 1][left] -= 1
				if right + 1 < n:
					ans[down + 1][right + 1] += 1
		for i in range(n - 1):
			for j in range(n):
				ans[i + 1][j] += ans[i][j]
		for i in range(n):
			for j in range(1, n):
				ans[i][j] += ans[i][j - 1]
		return ans


class Solution:

	def solveQueries(self, n, Queries):
		mat = [[0] * n for _ in range(n)]
		for (a, b, c, d) in Queries:
			for row in range(a, c + 1):
				mat[row][b] += 1
				if d + 1 < n:
					mat[row][d + 1] -= 1
		for col in range(1, n):
			for row in range(n):
				mat[row][col] += mat[row][col - 1]
		return mat


class Solution:

	def solveQueries(self, n, Queries):
		matrix = [[0 for i in range(n)] for j in range(n)]
		for (a, b, c, d) in Queries:
			for i in range(a, c + 1):
				matrix[i][b] += 1
				if d + 1 < n:
					matrix[i][d + 1] -= 1
		for i in range(n):
			for j in range(n - 1):
				matrix[i][j + 1] += matrix[i][j]
		return matrix


class Solution:

	def solveQueries(self, n, q):
		ans = [[0 for j in range(n)] for i in range(n)]
		x = len(q)
		for ele in q:
			strt_row = ele[0]
			strt_col = ele[1]
			end_row = ele[2]
			end_col = ele[3]
			if end_col >= n - 1:
				for i in range(strt_row, end_row + 1):
					ans[i][strt_col] += 1
			else:
				for i in range(strt_row, end_row + 1):
					ans[i][strt_col] += 1
					ans[i][end_col + 1] -= 1
		for i in range(n):
			for j in range(n):
				if j == 0:
					continue
				else:
					ans[i][j] += ans[i][j - 1]
		return ans


class Solution:

	def solveQueries(self, n, Queries):
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in Queries:
			a = i[0]
			b = i[1]
			c = i[2]
			d = i[3]
			for j in range(a, c + 1):
				dp[j][b] += 1
				if d + 1 < n:
					dp[j][d + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				dp[i][j] += dp[i][j - 1]
		return dp


class Solution:

	def solveQueries(self, n, Queries):
		matrix = [[0] * n for i in range(n)]
		for (i, j, m, l) in Queries:
			matrix[i][j] += 1
			if m + 1 < n and l + 1 < n:
				matrix[m + 1][l + 1] += 1
			if m + 1 < n:
				matrix[m + 1][j] -= 1
			if l + 1 < n:
				matrix[i][l + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				matrix[i][j] += matrix[i][j - 1]
		for i in range(1, n):
			for j in range(n):
				matrix[i][j] += matrix[i - 1][j]
		return matrix


class Solution:

	def solveQueries1(self, n, Queries):
		ans = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(len(Queries)):
			a = Queries[i][0]
			b = Queries[i][1]
			c = Queries[i][2]
			d = Queries[i][3]
			for j in range(a, c + 1):
				ans[j][b] += 1
				if d + 1 < n:
					ans[j][d + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				ans[i][j] += ans[i][j - 1]
		return ans

	def solveQueries(self, n, Queries):
		matrix = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(len(Queries)):
			a = Queries[i][0]
			b = Queries[i][1]
			c = Queries[i][2]
			d = Queries[i][3]
			for j in range(a, c + 1):
				matrix[j][b] += 1
				if d + 1 < n:
					matrix[j][d + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				matrix[i][j] += matrix[i][j - 1]
		return matrix


class Solution:

	def solveQueries(self, n, Queries):
		mat = [[0] * n for i in range(n)]
		for i in Queries:
			col = i[1]
			for j in range(i[0], i[2] + 1):
				mat[j][col] += 1
			if i[3] + 1 < n:
				for j in range(i[0], i[2] + 1):
					mat[j][i[3] + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				mat[i][j] += mat[i][j - 1]
		return mat


class Solution:

	def solveQueries(self, n, Queries):
		M = [[0 for i in range(n)] for j in range(n)]
		for k in Queries:
			b = k[1]
			d = k[3]
			a = k[0]
			c = k[2]
			M[a][b] += 1
			if d + 1 < n:
				M[a][d + 1] += -1
			if c + 1 < n:
				M[c + 1][b] += -1
			if c + 1 < n and d + 1 < n:
				M[c + 1][d + 1] += 1
		for i in range(n):
			for j in range(1, n):
				M[j][i] += M[j - 1][i]
		for i in range(n):
			for j in range(1, n):
				M[i][j] += M[i][j - 1]
		return M


class Solution:

	def solveQueries(self, n, Queries):
		ans = [[0] * n for _ in range(n)]
		for [up, left, down, right] in Queries:
			ans[up][left] += 1
			if right + 1 < n:
				ans[up][right + 1] -= 1
			if down + 1 < n:
				ans[down + 1][left] -= 1
				if right + 1 < n:
					ans[down + 1][right + 1] += 1
		for i in range(n - 1):
			for j in range(n):
				ans[i + 1][j] += ans[i][j]
		for i in range(n):
			for j in range(1, n):
				ans[i][j] += ans[i][j - 1]
		return ans
		for q in Queries:
			for i in range(q[0], q[2] + 1):
				for j in range(q[1], q[3] + 1):
					matrix[i][j] += 1
		return matrix


class Solution:

	def solveQueries(self, n, Queries):
		arr = [[0] * n for _ in range(n)]
		for i in range(len(Queries)):
			if Queries[i][3] + 1 < n:
				for j in range(Queries[i][0], Queries[i][2] + 1):
					arr[j][Queries[i][3] + 1] -= 1
			for j in range(Queries[i][0], Queries[i][2] + 1):
				arr[j][Queries[i][1]] += 1
		for i in range(n):
			for j in range(1, n):
				arr[i][j] += arr[i][j - 1]
		return arr


class Solution:

	def solveQueries(self, n, Queries):
		mat = [[0 for i in range(n)] for j in range(n)]
		for i in Queries:
			(st1, ed1, st2, ed2) = i
			k = 0
			while ed1 + k <= ed2:
				mat[st1][ed1 + k] += 1
				k += 1
			st2 += 1
			if st2 < n:
				k = 0
				while ed1 + k <= ed2:
					mat[st2][ed1 + k] += -1
					k += 1
		i = 1
		while i < n:
			for j in range(n):
				mat[i][j] += mat[i - 1][j]
			i += 1
		return mat


class Solution:

	def solveQueries(self, n, Queries):
		d = [[0 for i in range(n)] for j in range(n)]
		for q in Queries:
			for i in range(q[0], q[2] + 1):
				d[i][q[1]] = d[i][q[1]] + 1
				if q[3] + 1 < n:
					d[i][q[3] + 1] = d[i][q[3] + 1] - 1
		for i in range(n):
			for j in range(1, n):
				d[i][j] = d[i][j - 1] + d[i][j]
		return d


from itertools import accumulate

class Solution:

	def solveQueries(self, n, Queries):
		l = [[0 for i in range(n)] for j in range(n)]
		for (a, b, c, d) in Queries:
			for i in range(a, c + 1):
				l[i][b] += 1
				if d + 1 < n:
					l[i][d + 1] -= 1
		return [list(accumulate(r)) for r in l]


from collections import Counter

class Solution:

	def solveQueries(self, n, Queries):
		self.matrix = [[0] * n for i in range(n)]
		queries = Counter(map(tuple, Queries))
		for query in queries:
			self.update_matrix(query, queries[query])
		if n <= 1:
			return self.matrix
		for i in range(n):
			for j in range(1, n):
				self.matrix[i][j] += self.matrix[i][j - 1]
		return self.matrix

	def update_matrix(self, query, count):
		srow = 0
		scol = 1
		erow = 2
		ecol = 3
		for row in range(query[srow], query[erow] + 1):
			try:
				self.matrix[row][query[scol]] += count
				self.matrix[row][query[ecol] + 1] -= count
			except:
				pass
		return


class Solution:

	def isvalid(self, point, n):
		if point[0] >= 0 and point[0] < n and (point[1] >= 0) and (point[1] < n):
			return True
		else:
			return False

	def solveQueries(self, n, Queries):
		mat = [[0 for _ in range(n)] for _ in range(n)]
		for (a, b, c, d) in Queries:
			mat[a][b] += 1
			if self.isvalid([a, d + 1], n):
				mat[a][d + 1] -= 1
			if self.isvalid([c + 1, b], n):
				mat[c + 1][b] -= 1
			if self.isvalid([c + 1, d + 1], n):
				mat[c + 1][d + 1] += 1
		for j in range(1, n):
			for i in range(n):
				mat[i][j] += mat[i][j - 1]
		for j in range(n):
			for i in range(1, n):
				mat[i][j] += mat[i - 1][j]
		return mat


from itertools import accumulate

class Solution:

	def solveQueries(self, n, qs):
		diff = [[0] * n for _ in range(n)]
		for (a, b, c, d) in qs:
			for r in range(a, c + 1):
				diff[r][b] += 1
				if d + 1 < n:
					diff[r][d + 1] -= 1
		return [list(accumulate(r)) for r in diff]


class Solution:

	def solveQueries(self, n, Queries):
		dp = [[0] * (n + 1) for _ in range(n)]
		for (a, b, c, d) in Queries:
			for i in range(a, c + 1):
				dp[i][b] += 1
				dp[i][d + 1] += -1
		for i in range(n):
			temp = 0
			for j in range(n):
				temp += dp[i][j]
				dp[i][j] = temp
		ans = [[0] * n for _ in range(n)]
		for i in range(n):
			for j in range(n):
				ans[i][j] = dp[i][j]
		return ans


class Solution:

	def solveQueries(self, n, Queries):
		mat = [[0 for i in range(n)] for j in range(n)]
		for q in Queries:
			a = q[0]
			b = q[1]
			c = q[2]
			d = q[3]
			for row in range(a, c + 1):
				mat[row][b] += 1
				if d + 1 < n:
					mat[row][d + 1] -= 1
		for col in range(1, n):
			for row in range(n):
				mat[row][col] += mat[row][col - 1]
		return mat


class Solution:

	def solveQueries(self, n, Queries):
		tem = [[0] * n for i in range(n)]
		for (a, b, c, d) in Queries:
			for i in range(a, c + 1):
				tem[i][b] += 1
			if d < n - 1:
				for i in range(a, c + 1):
					tem[i][d + 1] -= 1
		ans = [[0] * n for i in range(n)]
		for i in range(n):
			counti = 0
			for j in range(n):
				counti += tem[i][j]
				ans[i][j] = counti
		return ans


class Solution:

	def solveQueries(self, n, Queries):
		tem_res = [[0 for i in range(n)] for i in range(n)]
		for (a, b, c, d) in Queries:
			for i in range(a, c + 1):
				tem_res[i][b] += 1
			if d < n - 1:
				for i in range(a, c + 1):
					tem_res[i][d + 1] -= 1
		result = [[0 for i in range(n)] for i in range(n)]
		for i in range(n):
			counti = 0
			for j in range(n):
				counti += tem_res[i][j]
				result[i][j] = counti
		return result


class Solution:

	def solveQueries(self, n, Queries):
		a = []
		pref = []
		for i in range(n):
			l = []
			for i in range(n):
				l.append(0)
			a.append(l)
		for l in Queries:
			a[l[0]][l[1]] += 1
			if l[3] < n - 1:
				a[l[0]][l[3] + 1] -= 1
			if l[2] < n - 1:
				a[l[2] + 1][l[1]] -= 1
			if l[3] < n - 1 and l[2] < n - 1:
				a[l[2] + 1][l[3] + 1] += 1
		for i in range(1, n):
			for j in range(n):
				a[i][j] += a[i - 1][j]
		for j in range(n):
			for i in range(1, n):
				a[j][i] += a[j][i - 1]
		return a


class Solution:

	def solveQueries(self, n, Queries):
		l = [[0 for j in range(n)] for i in range(n)]
		for i in range(len(Queries)):
			[a, b, c, d] = Queries[i]
			x = b
			for i in range(a, c + 1):
				l[i][b] += 1
				if d + 1 < n:
					l[i][d + 1] -= 1
		for j in range(1, n):
			for i in range(n):
				l[i][j] += l[i][j - 1]
		return l


class Solution:

	def solveQueries(self, n, Queries):
		mat = [[0 for i in range(n)] for j in range(n)]
		for (sx, sy, ex, ey) in Queries:
			mat[sx][sy] += 1
			if ex + 1 < n:
				mat[ex + 1][sy] -= 1
			if ey + 1 < n:
				mat[sx][ey + 1] -= 1
			if ex + 1 < n and ey + 1 < n:
				mat[ex + 1][ey + 1] += 1
		for x in range(n):
			for y in range(1, n):
				mat[x][y] += mat[x][y - 1]
		for x in range(1, n):
			for y in range(n):
				mat[x][y] += mat[x - 1][y]
		return mat


class Solution:

	def solveQueries(self, n, Queries):
		matrix = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(len(Queries)):
			a = Queries[i][0]
			b = Queries[i][1]
			c = Queries[i][2]
			d = Queries[i][3]
			for row in range(a, c + 1):
				matrix[row][b] += 1
				if d + 1 < n:
					matrix[row][d + 1] -= 1
		for col in range(1, n):
			for row in range(0, n):
				matrix[row][col] += matrix[row][col - 1]
		return matrix


class Solution:

	def solveQueries(self, n, Queries):
		dp = [[0 for i in range(n + 1)] for j in range(n)]
		for i in Queries:
			for j in range(i[0], i[2] + 1):
				dp[j][i[1]] += 1
				dp[j][i[3] + 1] -= 1
		ans = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			for j in range(n):
				if j != 0:
					dp[i][j] += dp[i][j - 1]
				ans[i][j] = dp[i][j]
		return ans


class Solution:

	def solveQueries(self, n, q):

		def updateQuery(from_x, from_y, to_x, to_y, k, aux):
			aux[from_x][from_y] += k
			if to_x + 1 < n:
				aux[to_x + 1][from_y] -= k
			if to_x + 1 < n and to_y + 1 < n:
				aux[to_x + 1][to_y + 1] += k
			if to_y + 1 < n:
				aux[from_x][to_y + 1] -= k

		def updatematrix(mat, aux):
			for i in range(n):
				for j in range(1, n):
					aux[i][j] += aux[i][j - 1]
			for i in range(n):
				for j in range(1, n):
					aux[j][i] += aux[j - 1][i]
			for i in range(n):
				for j in range(n):
					mat[i][j] += aux[i][j]
		aux = [[0 for i in range(n)] for j in range(n)]
		mat = [[0 for i in range(n)] for j in range(n)]
		for i in range(len(q)):
			updateQuery(q[i][0], q[i][1], q[i][2], q[i][3], 1, aux)
		updatematrix(mat, aux)
		return mat


class Solution:

	def solveQueries(self, n, queries):
		res = [[0 for j in range(n)] for i in range(n)]
		for (a, b, c, d) in Queries:
			res[a][b] += 1
			if c != n - 1:
				res[c + 1][b] -= 1
			if d != n - 1:
				res[a][d + 1] -= 1
			if c != n - 1 and d != n - 1:
				res[c + 1][d + 1] += 1
		for i in range(n):
			for j in range(n):
				if i:
					res[i][j] += res[i - 1][j]
				if j:
					res[i][j] += res[i][j - 1]
				if i and j:
					res[i][j] -= res[i - 1][j - 1]
		return res


class Solution:

	def solveQueries(self, n, Queries):
		ans = [[0 for i in range(n)] for i in range(n)]
		for i in Queries:
			(top, left, bottom, right) = i
			if right == n - 1:
				for p in range(top, bottom + 1):
					ans[p][left] += 1
			else:
				for p in range(top, bottom + 1):
					ans[p][left] += 1
					ans[p][right + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				ans[i][j] += ans[i][j - 1]
		return ans


class Solution:

	def solveQueries(self, n, Queries):
		ans = [[0] * n for _ in range(n)]
		for [up, left, down, right] in Queries:
			ans[up][left] += 1
			if right + 1 < n:
				ans[up][right + 1] -= 1
			if down + 1 < n:
				ans[down + 1][left] -= 1
				if right + 1 < n:
					ans[down + 1][right + 1] += 1
		for i in range(n - 1):
			for j in range(n):
				ans[i + 1][j] += ans[i][j]
		for i in range(n):
			for j in range(1, n):
				ans[i][j] += ans[i][j - 1]
		return ans
		res = [[0] * n for i in range(n)]
		for (x1, y1, x2, y2) in Queries:
			for x in range(x1, x2 + 1):
				for y in range(y1, y2 + 1):
					res[x][y] += 1
		return res


class Solution:

	def solveQueries(self, n, queries):
		l = [[0 for i in range(n)] for j in range(n)]
		for i in queries:
			(r1, r2) = (i[0], i[2])
			(c1, c2) = (i[1], i[3])
			for j in range(r1, r2 + 1):
				l[j][c1] += 1
				if c2 + 1 < n:
					l[j][c2 + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				l[i][j] += l[i][j - 1]
		return l


class Solution:

	def solveQueries(self, n, Queries):
		ans = [[0] * n for _ in range(n)]
		for [p, q, r, s] in Queries:
			ans[p][q] += 1
			if s + 1 < n:
				ans[p][s + 1] -= 1
			if r + 1 < n:
				ans[r + 1][q] -= 1
				if s + 1 < n:
					ans[r + 1][s + 1] += 1
		for i in range(n - 1):
			for j in range(n):
				ans[i + 1][j] += ans[i][j]
		for i in range(n):
			for j in range(1, n):
				ans[i][j] += ans[i][j - 1]
		return ans


class Solution:

	def solveQueries(self, n, Queries):
		res = [[0 for _ in range(n)] for _ in range(n)]
		for (x1, y1, x2, y2) in Queries:
			for x in range(x1, x2 + 1):
				res[x][y1] += 1
				if y2 + 1 < n:
					res[x][y2 + 1] -= 1
		for x in range(n):
			for y in range(1, n):
				res[x][y] += res[x][y - 1]
		return res


class Solution:

	def solveQueries(self, n, Queries):
		matrix = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
		rows = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
		cols = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
		for query in Queries:
			(a, b, c, d) = query
			rows[a][b] += 1
			rows[c + 1][b] -= 1
			cols[a][d + 1] -= 1
			cols[c + 1][d + 1] += 1
		for i in range(n):
			for j in range(1, n):
				rows[j][i] += rows[j - 1][i]
				cols[j][i] += cols[j - 1][i]
		for i in range(n):
			matrix[i][0] = rows[i][0] + cols[i][0]
		for i in range(1, n):
			for j in range(n):
				matrix[j][i] += matrix[j][i - 1] + rows[j][i] + cols[j][i]
		ans = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(n):
			for j in range(n):
				ans[i][j] = matrix[i][j]
		return ans


class Solution:

	def solveQueries(self, n, queries):
		arr = [[0 for i in range(n)] for i in range(n)]
		q = len(queries)
		for i in range(q):
			a = queries[i][0]
			b = queries[i][1]
			c = queries[i][2]
			d = queries[i][3]
			for j in range(a, c + 1):
				arr[j][b] += 1
				if d + 1 < n:
					arr[j][d + 1] -= 1
		for i in range(n):
			for j in range(1, n):
				arr[i][j] += arr[i][j - 1]
		return arr


import sys

def f(mat, Queries):
	for (xmin, ymin, xmax, ymax) in Queries:
		for i in range(xmin, xmax + 1):
			mat[i][ymin] += 1
			if ymax + 1 < n:
				mat[i][ymax + 1] -= 1
	ans = [[0 for y in range(n)] for x in range(n)]
	for j in range(n):
		if j == 0:
			for i in range(n):
				ans[i][j] = mat[i][j]
		else:
			for i in range(n):
				mat[i][j] = mat[i][j] + mat[i][j - 1]
				ans[i][j] = mat[i][j]
	return ans

class Solution:

	def solveQueries(self, n, Queries):
		mat = [[0 for j in range(n)] for i in range(n)]
		return f(mat, Queries)
sys.setrecursionlimit(1000000000)