Queries to count sum of rows and columns of a Matrix present in given ranges
Given a matrix A[][] of size N * M and a 2D array queries[][] consisting of Q queries of the form {L, R}, the task is to count the number of row-sums and column-sums which are an integer from the range [L, R].
Examples:
Input: N = 2, M = 2, A[][] = {{1, 4}, {2, 5}}, Q = 2, queries[][] = {{3, 7}, {3, 9}}
Output: 3 4
Explanation:
Sum of the first row = 1 + 4 = 5.
Sum of the second row = 2 + 5 = 7.
Sum of the first column= 1 + 2 = 3.
Sum of the second column = 4 + 5 = 9.Query 1: L = 3, R = 7:
Column sum present in the range = 3.
Row sums present in the range = {5, 7}.
Therefore, count is 3.
Query 2: L = 3, R = 9:
Column sum present in the range = {3, 9}.
Row sums present in the range = {5, 7}.
Therefore, count is 4.Input: N = 3, M = 2, A[][] = {{13, 3}, {9, 4}, {6, 10}}, Q = 2, queries[][] = {{10, 20}, {25, 35}}
Output: 4 1
Efficient approach: The idea is to traverse the matrix row-wise and column-wise and pre-calculate the sum of each row and column respectively. Traverse the array queries[][] and count the number of row-sums or column-sums present in the given ranges using Binary Search. Follow the steps below to solve the problem:
- Initialize two auxiliary arrays, say row_sum[] & col_sum[], to store the sum of rows and columns.
- Initialize another array, say sum_list[], to store all the row-sums and column-sums elements combined.
- Sort the array sum_list[] in ascending order.
- Traverse the array queries[] and for each query:
- Perform Binary Search to find the index, say i, of the leftmost sum, i.e. L.
- Again, perform Binary Search to find the index j of the rightmost sum, i.e R
- Print j – i + 1 as the result for the query.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to search for the // leftmost index of given number int left_search(vector< int > A, int num) { // Initialize low, high and ans int low = 0, high = A.size() - 1; int ans = 0; while (low <= high) { // Stores mid int mid = low + (high - low) / 2; // If A[mid] >= num if (A[mid] >= num) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } // Function to search for the // rightmost index of given number int right_search(vector< int > A, int num) { // Initialise low, high and ans int low = 0, high = A.size() - 1; int ans = high; while (low <= high) { // Stores mid int mid = low + (high - low) / 2; // If A[mid] <= num if (A[mid] <= num) { // Update ans ans = mid; // Update mid low = mid + 1; } else { // Update high high = mid - 1; } } return ans; } // Function to preprocess the matrix to execute the // queries void totalCount(vector<vector< int >> A, int N, int M, vector<vector< int >> queries, int Q) { // Stores the sum of each row vector< int > row_sum(N); // Stores the sum of each col vector< int > col_sum(N); // Traverse the matrix and calculate // sum of each row and column for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { row_sum[i] += A[i][j]; col_sum[j] += A[i][j]; } } vector< int > sum_list; // Insert all row sums in sum_list for ( int i = 0; i < N; i++) sum_list.push_back(row_sum[i]); // Insert all column sums in sum_list for ( int i = 0; i < M; i++) sum_list.push_back(col_sum[i]); // Sort the array in ascending order sort(sum_list.begin(), sum_list.end()); // Traverse the array queries[][] for ( int i = 0; i < Q; i++) { int L = queries[i][0]; int R = queries[i][1]; // Search the leftmost index of L int l = left_search(sum_list, L); // Search the rightmost index of R int r = right_search(sum_list, R); cout << r - l + 1 << " " ; } } // Driver Code int main() { // Given dimensions of matrix int N = 3, M = 2; // Given matrix vector<vector< int >> A = {{13, 3}, {9, 4}, {6, 10}}; // Given number of queries int Q = 2; // Given queries vector<vector< int >> queries = {{10, 20}, {25, 35}}; // Function call to count the // number row-sums and column-sums // present in the given ranges totalCount(A, N, M, queries, Q); } // This code is contributed by nirajgusain5 |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to preprocess the matrix to execute the // queries static void totalCount( int [][] A, int N, int M, int [][] queries, int Q) { // Stores the sum of each row int row_sum[] = new int [N]; // Stores the sum of each col int col_sum[] = new int [M]; // Traverse the matrix and calculate // sum of each row and column for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { row_sum[i] += A[i][j]; col_sum[j] += A[i][j]; } } ArrayList<Integer> sum_list = new ArrayList<>(); // Insert all row sums in sum_list for ( int i = 0 ; i < N; i++) sum_list.add(row_sum[i]); // Insert all column sums in sum_list for ( int i = 0 ; i < M; i++) sum_list.add(col_sum[i]); // Sort the array in ascending order Collections.sort(sum_list); // Traverse the array queries[][] for ( int i = 0 ; i < Q; i++) { int L = queries[i][ 0 ]; int R = queries[i][ 1 ]; // Search the leftmost index of L int l = left_search(sum_list, L); // Search the rightmost index of R int r = right_search(sum_list, R); System.out.print(r - l + 1 + " " ); } } // Function to search for the // leftmost index of given number static int left_search( ArrayList<Integer> A, int num) { // Initialize low, high and ans int low = 0 , high = A.size() - 1 ; int ans = 0 ; while (low <= high) { // Stores mid int mid = low + (high - low) / 2 ; // If A[mid] >= num if (A.get(mid) >= num) { ans = mid; high = mid - 1 ; } else { low = mid + 1 ; } } return ans; } // Function to search for the // rightmost index of given number static int right_search( ArrayList<Integer> A, int num) { // Initialise low, high and ans int low = 0 , high = A.size() - 1 ; int ans = high; while (low <= high) { // Stores mid int mid = low + (high - low) / 2 ; // If A[mid] <= num if (A.get(mid) <= num) { // Update ans ans = mid; // Update mid low = mid + 1 ; } else { // Update high high = mid - 1 ; } } return ans; } // Driver Code public static void main(String[] args) { // Given dimensions of matrix int N = 3 , M = 2 ; // Given matrix int A[][] = { { 13 , 3 }, { 9 , 4 }, { 6 , 10 } }; // Given number of queries int Q = 2 ; // Given queries int queries[][] = { { 10 , 20 }, { 25 , 35 } }; // Function call to count the // number row-sums and column-sums // present in the given ranges totalCount(A, N, M, queries, Q); } } |
Python3
# Python3 program for the above approach from collections import deque from bisect import bisect_left, bisect_right # Function to preprocess the matrix to execute the # queries def totalCount(A, N, M, queries, Q): # Stores the sum of each row row_sum = [ 0 ] * N # Stores the sum of each col col_sum = [ 0 ] * M # Traverse the matrix and calculate # sum of each row and column for i in range (N): for j in range (M): row_sum[i] + = A[i][j] col_sum[j] + = A[i][j] sum_list = [] # Insert all row sums in sum_list for i in range (N): sum_list.append(row_sum[i]) # Insert all column sums in sum_list for i in range (M): sum_list.append(col_sum[i]) # Sort the array in ascending order sum_list = sorted (sum_list) # Traverse the array queries[][] for i in range (Q): L = queries[i][ 0 ] R = queries[i][ 1 ] # Search the leftmost index of L l = left_search(sum_list, L) # Search the rightmost index of R r = right_search(sum_list, R) print (r - l + 1 , end = " " ) # Function to search for the # leftmost index of given number def left_search(A, num): # Initialize low, high and ans low, high = 0 , len (A) - 1 ans = 0 while (low < = high): # Stores mid mid = low + (high - low) / / 2 # If A[mid] >= num if (A[mid] > = num): ans = mid high = mid - 1 else : low = mid + 1 return ans # Function to search for the # rightmost index of given number def right_search(A, num): # Initialise low, high and ans low, high = 0 , len (A) - 1 ans = high while (low < = high): # Stores mid mid = low + (high - low) / / 2 # If A[mid] <= num if (A[mid] < = num): # Update ans ans = mid # Update mid low = mid + 1 else : # Update high high = mid - 1 return ans # Driver Code if __name__ = = '__main__' : # Given dimensions of matrix N, M = 3 , 2 # Given matrix A = [ [ 13 , 3 ], [ 9 , 4 ], [ 6 , 10 ] ] # Given number of queries Q = 2 # Given queries queries = [ [ 10 , 20 ], [ 25 , 35 ] ] # Function call to count the # number row-sums and column-sums # present in the given ranges totalCount(A, N, M, queries, Q) # This code is contributed by mohit kumar 29. |
C#
using System; using System.Collections.Generic; class GFG { // Function to preprocess the matrix to execute the // queries static void totalCount( int [,] A, int N, int M, int [,] queries, int Q) { // Stores the sum of each row int []row_sum = new int [N]; // Stores the sum of each col int []col_sum = new int [M]; // Traverse the matrix and calculate // sum of each row and column for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { row_sum[i] += A[i,j]; col_sum[j] += A[i,j]; } } List< int > sum_list = new List< int >(); // Insert all row sums in sum_list for ( int i = 0; i < N; i++) sum_list.Add(row_sum[i]); // Insert all column sums in sum_list for ( int i = 0; i < M; i++) sum_list.Add(col_sum[i]); // Sort the array in ascending order sum_list.Sort(); // Traverse the array queries[][] for ( int i = 0; i < Q; i++) { int L = queries[i,0]; int R = queries[i,1]; // Search the leftmost index of L int l = left_search(sum_list, L); // Search the rightmost index of R int r = right_search(sum_list, R); Console.Write(r - l + 1 + " " ); } } // Function to search for the // leftmost index of given number static int left_search(List< int > A, int num) { // Initialize low, high and ans int low = 0, high = A.Count- 1; int ans = 0; while (low <= high) { // Stores mid int mid = low + (high - low) / 2; // If A[mid] >= num if (A[mid] >= num) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } // Function to search for the // rightmost index of given number static int right_search( List< int > A, int num) { // Initialise low, high and ans int low = 0, high = A.Count- 1; int ans = high; while (low <= high) { // Stores mid int mid = low + (high - low) / 2; // If A[mid] <= num if (A[mid] <= num) { // Update ans ans = mid; // Update mid low = mid + 1; } else { // Update high high = mid - 1; } } return ans; } //driver code static void Main() { int N = 3, M = 2; // Given matrix int [,]A = new int [,]{ { 13, 3 },{ 9, 4 },{ 6, 10 } }; // Given number of queries int Q = 2; // Given queries int [,]queries = new int [,]{ { 10, 20 }, { 25, 35 } }; // Function call to count the // number row-sums and column-sums // present in the given ranges totalCount(A, N, M, queries, Q); } } //This code is contributed by SoumikMondal |
Javascript
<script> // Javascript program for the above approach // Function to preprocess the matrix to execute the // queries function totalCount(A,N,M,queries,Q) { // Stores the sum of each row let row_sum = new Array(N); // Stores the sum of each col let col_sum = new Array(M); for (let i=0;i<N;i++) row_sum[i]=0; for (let j=0;j<M;j++) col_sum[j]=0; // Traverse the matrix and calculate // sum of each row and column for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { row_sum[i] += A[i][j]; col_sum[j] += A[i][j]; } } let sum_list=[]; // Insert all row sums in sum_list for (let i = 0; i < N; i++) sum_list.push(row_sum[i]); // Insert all column sums in sum_list for (let i = 0; i < M; i++) sum_list.push(col_sum[i]); // Sort the array in ascending order (sum_list).sort( function (a,b){ return a-b;}); // Traverse the array queries[][] for (let i = 0; i < Q; i++) { let L = queries[i][0]; let R = queries[i][1]; // Search the leftmost index of L let l = left_search(sum_list, L); // Search the rightmost index of R let r = right_search(sum_list, R); document.write(r - l + 1 + " " ); } } // Function to search for the // leftmost index of given number function left_search(A,num) { // Initialize low, high and ans let low = 0, high = A.length - 1; let ans = 0; while (low <= high) { // Stores mid let mid = low + Math.floor((high - low) / 2); // If A[mid] >= num if (A[mid] >= num) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } // Function to search for the // rightmost index of given number function right_search(A,num) { // Initialise low, high and ans let low = 0, high = A.length - 1; let ans = high; while (low <= high) { // Stores mid let mid = low + Math.floor((high - low) / 2); // If A[mid] <= num if (A[mid] <= num) { // Update ans ans = mid; // Update mid low = mid + 1; } else { // Update high high = mid - 1; } } return ans; } // Given dimensions of matrix let N = 3, M = 2; // Given matrix let A=[[ 13, 3 ],[ 9, 4 ],[ 6, 10 ] ]; // Given number of queries let Q = 2; let queries=[[ 10, 20 ], [ 25, 35 ]]; // Function call to count the // number row-sums and column-sums // present in the given ranges totalCount(A, N, M, queries, Q); // This code is contributed by unknown2108 </script> |
4 1
Time Complexity: O(Q * log(N * M))
Auxiliary Space: O(N * M)
Contact Us