Given a 2D matrix mat[][] of size N*M and Q queries of the form {x1, y1, x2, y2, K}. For each query, the task is to add the value K to submatrix from cell (x1, y1) to (x2, y2). Print the matrix after all the queries performed.
Examples:
Input: N = 3, M = 4, mat[][] = {{1, 0, 1, 2}, {0, 2, 4, 1}, {1, 2, 1, 0}}, Q = 1, Queries[][] = {{0, 0, 1, 1, 2}}
Output:
3 2 1 2
2 4 4 1
1 2 1 0
Explanation:
There is only one query i.e., updating the submatrix from cell mat[0][0] to mat[1][1] by increment of 2, the matrix becomes:
3 2 1 2
2 4 4 1
1 2 1 0Input: N = 2, M = 3, mat[][] = {{3, 2, 1}, {2, 4, 4}}, Q = 1, Queries[][] = { {0, 1, 1, 2, -1}, {0, 0, 1, 1, 5}}
Output:
8 6 0
7 8 3
Explanation:
For query 1, i.e., updating the submatrix from cell mat[0][1] to mat[1][2] by increment of (-1), the matrix becomes:
3 1 0
2 3 3
For query 2, i.e., updating the submatrix from cell mat[0][0] to mat[2][2] by increment of 5, the matrix becomes:
8 6 0
7 8 3
Naive Approach: The simplest approach is to iterate over the submatrix and add K to all elements from mat[x1][y1] to mat[x2][y2] for each query. Print the matrix after the above operations.
Time Complexity: O(N*M*Q)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use an auxiliary matrix to perform the update operations on the corners of the submatrix cells and then find the prefix sum of the matrix to get the resultant matrix. Below are the steps:
- Initialize all elements of the auxiliary matrix say aux[][] to 0.
- For each query {x1, y1, x2, y2, K} update the auxiliary matrix as:
- aux[x1][y1] += K
- if(x2 + 1 < N) then aux[x2 + 1][y1] -= K
- if(x2 + 1 < N && y2 + 1 < N) then aux[x2 + 1][y2 + 1] += K
- if(y2 + 1 < N) then aux[x1][y2 + 1] -= K
- Find the prefix sum of each row of the auxiliary matrix.
- Find the prefix sum of each column of the auxiliary matrix.
- Now, update the auxiliary matrix as the sum of elements at each respective cell of the auxiliary and the given matrix.
- Print the auxiliary matrix after all the above operations.
Below is the illustration for how auxiliary matrix is created and updated for query[][] = {{0, 0, 1, 1, 2}, {0, 1, 2, 3, -1}}:
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 3#define M 4// Query data typestruct query { int x1, x2, y1, y2, K;};// Function to update the given queryvoid updateQuery(int from_x, int from_y, int to_x, int to_y, int k, int aux[][M]){ // Update top cell aux[from_x][from_y] += k; // Update bottom left cell if (to_x + 1 < N) aux[to_x + 1][from_y] -= k; // Update bottom right cell if (to_x + 1 < N && to_y + 1 < M) aux[to_x + 1][to_y + 1] += k; // Update top right cell if (to_y + 1 < M) aux[from_x][to_y + 1] -= k;}// Function that updates the matrix// mat[][] by adding elements of aux[][]void updateMatrix(int mat[][M], int aux[][M]){ // Compute the prefix sum of all columns for (int i = 0; i < N; i++) { for (int j = 1; j < M; j++) { aux[i][j] += aux[i][j - 1]; } } // Compute the prefix sum of all rows for (int i = 0; i < M; i++) { for (int j = 1; j < N; j++) { aux[j][i] += aux[j - 1][i]; } } // Get the final matrix by adding // mat and aux matrix at each cell for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { mat[i][j] += aux[i][j]; } }}// Function that prints matrix mat[]void printMatrix(int mat[][M]){ // Traverse each row for (int i = 0; i < N; i++) { // Traverse each columns for (int j = 0; j < M; j++) { cout << mat[i][j] << " "; } cout << "\n"; }}// Function that performs each query in// the given matrix and print the updated// matrix after each operation performedvoid matrixQuery(int mat[][M], int Q, query q[]){ // Initialize all elements to 0 int aux[N][M] = {}; // Update auxiliary matrix // by traversing each query for (int i = 0; i < Q; i++) { // Update Query updateQuery(q[i].x1, q[i].x2, q[i].y1, q[i].y2, q[i].K, aux); } // Compute the final answer updateMatrix(mat, aux); // Print the updated matrix printMatrix(mat);}// Driver Codeint main(){ // Given Matrix int mat[N][M] = { { 1, 0, 1, 2 }, { 0, 2, 4, 1 }, { 1, 2, 1, 0 } }; int Q = 1; // Given Queries query q[] = { { 0, 0, 1, 1, 2 } }; // Function Call matrixQuery(mat, Q, q); return 0;} |
Java
// Java program for the above approachclass GFG{static final int N = 3;static final int M = 4;// Query data typestatic class query { int x1, x2, y1, y2, K; public query(int x1, int x2, int y1, int y2, int k) { this.x1 = x1; this.x2 = x2; this.y1 = y1; this.y2 = y2; K = k; }};// Function to update the given querystatic void updateQuery(int from_x, int from_y, int to_x, int to_y, int k, int aux[][]){ // Update top cell aux[from_x][from_y] += k; // Update bottom left cell if (to_x + 1 < N) aux[to_x + 1][from_y] -= k; // Update bottom right cell if (to_x + 1 < N && to_y + 1 < M) aux[to_x + 1][to_y + 1] += k; // Update top right cell if (to_y + 1 < M) aux[from_x][to_y + 1] -= k;}// Function that updates the matrix// mat[][] by adding elements of aux[][]static void updateMatrix(int mat[][], int aux[][]){ // Compute the prefix sum of all columns for (int i = 0; i < N; i++) { for (int j = 1; j < M; j++) { aux[i][j] += aux[i][j - 1]; } } // Compute the prefix sum of all rows for (int i = 0; i < M; i++) { for (int j = 1; j < N; j++) { aux[j][i] += aux[j - 1][i]; } } // Get the final matrix by adding // mat and aux matrix at each cell for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { mat[i][j] += aux[i][j]; } }}// Function that prints matrix mat[]static void printMatrix(int mat[][]){ // Traverse each row for (int i = 0; i < N; i++) { // Traverse each columns for (int j = 0; j < M; j++) { System.out.print(mat[i][j] + " "); } System.out.print("\n"); }}// Function that performs each query in// the given matrix and print the updated// matrix after each operation performedstatic void matrixQuery(int mat[][], int Q, query q[]){ // Initialize all elements to 0 int [][]aux = new int[N][M]; // Update auxiliary matrix // by traversing each query for (int i = 0; i < Q; i++) { // Update Query updateQuery(q[i].x1, q[i].x2, q[i].y1, q[i].y2, q[i].K, aux); } // Compute the final answer updateMatrix(mat, aux); // Print the updated matrix printMatrix(mat);}// Driver Codepublic static void main(String[] args){ // Given Matrix int mat[][] = {{1, 0, 1, 2}, {0, 2, 4, 1}, {1, 2, 1, 0}}; int Q = 1; // Given Queries query q[] = {new query(0, 0, 1, 1, 2 )}; // Function Call matrixQuery(mat, Q, q);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Query data type# Function to update the given querydef updateQuery(from_x, from_y, to_x, to_y, k, aux): # Update top cell aux[from_x][from_y] += k # Update bottom left cell if (to_x + 1 < 3): aux[to_x + 1][from_y] -= k # Update bottom right cell if (to_x + 1 < 3 and to_y + 1 < 4): aux[to_x + 1][to_y + 1] += k # Update top right cell if (to_y + 1 < 4): aux[from_x][to_y + 1] -= k # return aux# Function that updates the matrix# mat[][] by adding elements of aux[][]def updatematrix(mat, aux): # Compute the prefix sum of all columns for i in range(3): for j in range(1, 4): aux[i][j] += aux[i][j - 1] # Compute the prefix sum of all rows for i in range(4): for j in range(1, 3): aux[j][i] += aux[j - 1][i] # Get the final matrix by adding # mat and aux matrix at each cell for i in range(3): for j in range(4): mat[i][j] += aux[i][j] # return mat# Function that prints matrix mat[]def printmatrix(mat): # Traverse each row for i in range(3): # Traverse each columns for j in range(4): print(mat[i][j], end = " ") print()# Function that performs each query in# the given matrix and print the updated# matrix after each operation performeddef matrixQuery(mat, Q, q): # Initialize all elements to 0 aux = [[ 0 for i in range(4)] for i in range(3)] # Update auxiliary matrix # by traversing each query for i in range(Q): # Update Query updateQuery(q[i][0], q[i][1], q[i][2], q[i][3], q[i][4], aux) # Compute the final answer updatematrix(mat, aux) # Print the updated matrix printmatrix(mat)# Driver Codeif __name__ == '__main__': # Given 4atrix mat = [ [ 1, 0, 1, 2 ], [ 0, 2, 4, 1 ], [ 1, 2, 1, 0 ] ] Q = 1 # Given Queries q = [ [0, 0, 1, 1, 2 ] ] # Function Call matrixQuery(mat, Q, q)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ static readonly int N = 3;static readonly int M = 4;// Query data typeclass query { public int x1, x2, y1, y2, K; public query(int x1, int x2, int y1, int y2, int k) { this.x1 = x1; this.x2 = x2; this.y1 = y1; this.y2 = y2; K = k; }};// Function to update the given querystatic void updateQuery(int from_x, int from_y, int to_x, int to_y, int k, int [,]aux){ // Update top cell aux[from_x, from_y] += k; // Update bottom left cell if (to_x + 1 < N) aux[to_x + 1, from_y] -= k; // Update bottom right cell if (to_x + 1 < N && to_y + 1 < M) aux[to_x + 1, to_y + 1] += k; // Update top right cell if (to_y + 1 < M) aux[from_x, to_y + 1] -= k;}// Function that updates the matrix// [,]mat by adding elements of aux[,]static void updateMatrix(int [,]mat, int [,]aux){ // Compute the prefix sum of all columns for(int i = 0; i < N; i++) { for(int j = 1; j < M; j++) { aux[i, j] += aux[i, j - 1]; } } // Compute the prefix sum of all rows for(int i = 0; i < M; i++) { for(int j = 1; j < N; j++) { aux[j, i] += aux[j - 1, i]; } } // Get the readonly matrix by adding // mat and aux matrix at each cell for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { mat[i, j] += aux[i, j]; } }}// Function that prints matrix []matstatic void printMatrix(int [,]mat){ // Traverse each row for(int i = 0; i < N; i++) { // Traverse each columns for(int j = 0; j < M; j++) { Console.Write(mat[i, j] + " "); } Console.Write("\n"); }}// Function that performs each query in// the given matrix and print the updated// matrix after each operation performedstatic void matrixQuery(int [,]mat, int Q, query []q){ // Initialize all elements to 0 int [,]aux = new int[N, M]; // Update auxiliary matrix // by traversing each query for(int i = 0; i < Q; i++) { // Update Query updateQuery(q[i].x1, q[i].x2, q[i].y1, q[i].y2, q[i].K, aux); } // Compute the readonly answer updateMatrix(mat, aux); // Print the updated matrix printMatrix(mat);}// Driver Codepublic static void Main(String[] args){ // Given Matrix int [,]mat = { { 1, 0, 1, 2 }, { 0, 2, 4, 1 }, { 1, 2, 1, 0 } }; int Q = 1; // Given Queries query []q = {new query( 0, 0, 1, 1, 2 )}; // Function call matrixQuery(mat, Q, q);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approachlet N = 3;let M = 4;// Query data typeclass query{ constructor(x1,x2,y1,y2,k) { this.x1 = x1; this.x2 = x2; this.y1 = y1; this.y2 = y2; this.K = k; }}// Function to update the given queryfunction updateQuery(from_x,from_y,to_x,to_y,k,aux){ // Update top cell aux[from_x][from_y] += k; // Update bottom left cell if (to_x + 1 < N) aux[to_x + 1][from_y] -= k; // Update bottom right cell if (to_x + 1 < N && to_y + 1 < M) aux[to_x + 1][to_y + 1] += k; // Update top right cell if (to_y + 1 < M) aux[from_x][to_y + 1] -= k;}// Function that updates the matrix// mat[][] by adding elements of aux[][]function updateMatrix(mat,aux){ // Compute the prefix sum of all columns for (let i = 0; i < N; i++) { for (let j = 1; j < M; j++) { aux[i][j] += aux[i][j - 1]; } } // Compute the prefix sum of all rows for (let i = 0; i < M; i++) { for (let j = 1; j < N; j++) { aux[j][i] += aux[j - 1][i]; } } // Get the final matrix by adding // mat and aux matrix at each cell for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { mat[i][j] += aux[i][j]; } }}// Function that prints matrix mat[]function printMatrix(mat){ // Traverse each row for (let i = 0; i < N; i++) { // Traverse each columns for (let j = 0; j < M; j++) { document.write(mat[i][j] + " "); } document.write("<br>"); }}// Function that performs each query in// the given matrix and print the updated// matrix after each operation performedfunction matrixQuery(mat,Q,q){ // Initialize all elements to 0 let aux = new Array(N); for(let i=0;i<N;i++) { aux[i]=new Array(M); for(let j=0;j<M;j++) { aux[i][j]=0; } } // Update auxiliary matrix // by traversing each query for (let i = 0; i < Q; i++) { // Update Query updateQuery(q[i].x1, q[i].x2, q[i].y1, q[i].y2, q[i].K, aux); } // Compute the final answer updateMatrix(mat, aux); // Print the updated matrix printMatrix(mat);}// Driver Code// Given Matrixlet mat = [[1, 0, 1, 2],[0, 2, 4, 1],[1, 2, 1, 0]];let Q = 1;// Given Querieslet q = [new query(0, 0, 1, 1, 2 )];// Function CallmatrixQuery(mat, Q, q);// This code is contributed by unknown2108</script> |
Output:
3 2 1 2 2 4 4 1 1 2 1 0
Time Complexity: O(Q + N*M)
Auxiliary Space: O(N*M)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
