Final Matrix after incrementing all cells of given Submatrices

Last Updated : 26 Dec, 2022

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

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

Time Complexity: O(N²) We are evaluating the final elements from the 1D array of rows and columns.
Auxiliary space: O(N²) We are storing the final elements after all the queries in a matrix.