Final Matrix after incrementing all cells of given Submatrices
Given a matrix of dimension N*N whose all cells are initially 0. You are given Q queries, each of type {a, b, c, d} where (a, b) is the top-left cell and (c, d) is the bottom-right cell of a submatrix whose every cell needs to be incremented by 1. The task is to find the final matrix after incrementing all the submatrices.
Examples:
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.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.
Approach:
We will be using Difference Array algorithm which is used in 1D array. We will be using this extended algorithm for the 2D matrix. By pre-processing the queries we will be able to get the whole matrix after queries.
Follow the steps mentioned below to implement the idea:
- Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0].
- We will be creating two 1D arrays one which stores the updates on the row and another one stores the updates on the column.
- After processing the queries we will now derive the matrix.
- For the first element of the row and column do A[0] = D[0] and for rest of the elements, do A[i] = A[i-1] + D[i]. This will be same implemented in the 2D matrix for each row and column.
- After that evaluate the first row and then we will be able to get all the elements by using the below formula
matrix[j][i] += matrix[j][i – 1] + row[j][i] + col[j][i].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to solve q Queries vector<vector< int > > solveQueries( int N, vector<vector< int > > Queries) { // Initialize vectors vector<vector< int > > matrix(N + 2, vector< int >(N + 2, 0)); vector<vector< int > > row(N + 2, vector< int >(N + 2, 0)); vector<vector< int > > col(N + 2, vector< int >(N + 2, 0)); // Traverse over the queries for ( auto i : Queries) { int a = i[0]; int b = i[1]; int c = i[2]; int d = i[3]; row[a][b]++; row[b]--; col[a][d + 1]--; col[d + 1]++; } // Update row and col vector for ( int i = 0; i < N; i++) { for ( int j = 1; j < N; j++) { row[j][i] += row[j - 1][i]; col[j][i] += col[j - 1][i]; } } // Traverse and update matrix vector for ( int i = 0; i < N; i++) { matrix[i][0] = row[i][0] + col[i][0]; } for ( int i = 1; i <= N; i++) { for ( int j = 0; j < N; j++) { matrix[j][i] += matrix[j][i - 1] + row[j][i] + col[j][i]; } } // resultant answer vector vector<vector< int > > res(N, vector< int >(N, 0)); for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) res[i][j] = matrix[i][j]; return res; } // function to print resultant matrix void printAns(vector<vector< int > >& res) { for ( int i = 0; i < res.size(); i++) { for ( int j = 0; j < res[0].size(); j++) { cout << res[i][j] << " " ; } cout << endl; } } // Driver Code int main() { int N = 6; int q = 6; vector<vector< int > > 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 } }; vector<vector< int > > res; res = solveQueries(N, Queries); printAns(res); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to solve q Queries public static int [][] solveQueries( int N, int Queries[][]) { // Initialize arrays int matrix[][] = new int [N + 2 ][N + 2 ]; int row[][] = new int [N + 2 ][N + 2 ]; int col[][] = new int [N + 2 ][N + 2 ]; // Traverse over the queries for ( int i[] : Queries) { int a = i[ 0 ]; int b = i[ 1 ]; int c = i[ 2 ]; int d = i[ 3 ]; row[a][b]++; row[b]--; col[a][d + 1 ]--; col[d + 1 ]++; } // Update row and col array for ( int i = 0 ; i < N; i++) { for ( int j = 1 ; j < N; j++) { row[j][i] += row[j - 1 ][i]; col[j][i] += col[j - 1 ][i]; } } // Traverse and update matrix for ( int i = 0 ; i < N; i++) { matrix[i][ 0 ] = row[i][ 0 ] + col[i][ 0 ]; } for ( int i = 1 ; i <= N; i++) { for ( int j = 0 ; j < N; j++) { matrix[j][i] += matrix[j][i - 1 ] + row[j][i] + col[j][i]; } } // resultant answer vector int res[][] = new int [N][N]; for ( int i = 0 ; i < N; i++) for ( int j = 0 ; j < N; j++) res[i][j] = matrix[i][j]; return res; } // function to print resultant matrix public static void printAns( int res[][]) { for ( int i = 0 ; i < res.length; i++) { for ( int j = 0 ; j < res[ 0 ].length; j++) { System.out.print(res[i][j] + " " ); } System.out.println(); } } // Driver Code public static void main(String[] args) { int N = 6 ; int q = 6 ; int 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 } }; int res[][] = solveQueries(N, Queries); printAns(res); } } // This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach # Function to solve q Queries def solveQueries(N, Queries): # // Initialize vectors matrix = [ 0 ] * (N + 2 ) # (N + 2); for i in range ( 0 , len (matrix)): matrix[i] = [ 0 ] * (N + 2 ) row = [ 0 ] * (N + 2 ) for i in range ( 0 , len (row)): row[i] = [ 0 ] * (N + 2 ) col = [ 0 ] * (N + 2 ) for i in range ( 0 , len (col)): col[i] = [ 0 ] * (N + 2 ) # // Traverse over the queries for i in range ( 0 , len (Queries)): a = Queries[i][ 0 ] b = Queries[i][ 1 ] c = Queries[i][ 2 ] d = Queries[i][ 3 ] row[a][b] + = 1 row[b] - = 1 col[a][d + 1 ] - = 1 col[d + 1 ] + = 1 for i in range ( 0 , N): for j in range ( 1 , N): row[j][i] + = row[j - 1 ][i] col[j][i] + = col[j - 1 ][i] # // Traverse and update matrix vector for i in range ( 0 , N): matrix[i][ 0 ] = row[i][ 0 ] + col[i][ 0 ] for i in range ( 1 , N + 1 ): for j in range ( 0 , N): matrix[j][i] + = (matrix[j][i - 1 ] + row[j][i] + col[j][i]) res = [ 0 ] * (N) for i in range ( 0 , len (res)): res[i] = [ 0 ] * N # new Array(N).fill(0); for i in range ( 0 , N): for j in range ( 0 , N): res[i][j] = matrix[i][j] return res # // function to print resultant matri def printAns(res): for i in range ( 0 , len (res)): for j in range ( 0 , len (res[ 0 ])): print (res[i][j],end = " " ) print () # Driver Code 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 ]] res = solveQueries(N, Queries) printAns(res) # This code is contributed by ksam24000 |
C#
// C# code to implement the approach using System; class GFG { // Function to solve q Queries public static int [, ] solveQueries( int N, int [, ] Queries) { // Initialize arrays int [, ] matrix = new int [N + 2, N + 2]; int [, ] row = new int [N + 2, N + 2]; int [, ] col = new int [N + 2, N + 2]; // Traverse over the queries for ( int i = 0; i < Queries.GetLength(0); i++) { int a = Queries[i, 0]; int b = Queries[i, 1]; int c = Queries[i, 2]; int d = Queries[i, 3]; row[a, b]++; row--; col[a, d + 1]--; col++; } // Update row and col array for ( int i = 0; i < N; i++) { for ( int j = 1; j < N; j++) { row[j, i] += row[j - 1, i]; col[j, i] += col[j - 1, i]; } } // Traverse and update matrix for ( int i = 0; i < N; i++) { matrix[i, 0] = row[i, 0] + col[i, 0]; } for ( int i = 1; i <= N; i++) { for ( int j = 0; j < N; j++) { matrix[j, i] += matrix[j, i - 1] + row[j, i] + col[j, i]; } } // resultant answer vector int [, ] res = new int [N, N]; for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) res[i, j] = matrix[i, j]; return res; } // function to print resultant matrix static void printAns( int [, ] res) { for ( int i = 0; i < res.GetLength(0); i++) { for ( int j = 0; j < res.GetLength(1); j++) { Console.Write(res[i, j] + " " ); } Console.WriteLine(); } } // Driver Code public static void Main() { int N = 6; int q = 6; int [, ] 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 } }; int [, ] res = solveQueries(N, Queries); printAns(res); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code for the above approach // Function to solve q Queries function solveQueries(N, Queries) { // Initialize vectors let matrix = new Array(N + 2); for (let i = 0; i < matrix.length; i++) { matrix[i] = new Array(N + 2).fill(0); } let row = new Array(N + 2); for (let i = 0; i < row.length; i++) { row[i] = new Array(N + 2).fill(0); } let col = new Array(N + 2); for (let i = 0; i < col.length; i++) { col[i] = new Array(N + 2).fill(0); } // Traverse over the queries for (let i = 0; i < Queries.length; i++) { let a = Queries[i][0]; let b = Queries[i][1]; let c = Queries[i][2]; let d = Queries[i][3]; row[a][b]++; row[b]--; col[a][d + 1]--; col[d + 1]++; } // Update row and col vector for (let i = 0; i < N; i++) { for (let j = 1; j < N; j++) { row[j][i] += row[j - 1][i]; col[j][i] += col[j - 1][i]; } } // Traverse and update matrix vector for (let i = 0; i < N; i++) { matrix[i][0] = row[i][0] + col[i][0]; } for (let i = 1; i <= N; i++) { for (let j = 0; j < N; j++) { matrix[j][i] += matrix[j][i - 1] + row[j][i] + col[j][i]; } } // resultant answer vector let res = new Array(N); for (let i = 0; i < res.length; i++) { res[i] = new Array(N).fill(0); } for (let i = 0; i < N; i++) for (let j = 0; j < N; j++) res[i][j] = matrix[i][j]; return res; } // function to print resultant matrix function printAns(res) { for (let i = 0; i < res.length; i++) { for (let j = 0; j < res[0].length; j++) { console.log(res[i][j] + " " ) } console.log( "<br>" ) } } // Driver Code let N = 6; let q = 6; let 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]]; let res; res = solveQueries(N, Queries); printAns(res); // This code is contributed by Potta Lokesh |
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
Time Complexity: O(N2) We are evaluating the final elements from the 1D array of rows and columns.
Auxiliary space: O(N2) We are storing the final elements after all the queries in a matrix.