Queries to count sum of rows and columns of a Matrix present in given ranges | Java program for the above approach ; Function to preprocess the matrix to execute the queries ; Stores the sum of each row ; Stores the sum of each col ; Traverse the matrix and calculate sum of each row and column ; Insert all row sums in sum_list ; Insert all column sums in sum_list ; Sort the array in ascending order ; Traverse the array queries [ ] [ ] ; Search the leftmost index of L ; Search the rightmost index of R ; Function to search for the leftmost index of given number ; Initialize low , high and ans ; Stores mid ; If A [ mid ] >= num ; Function to search for the rightmost index of given number ; Initialise low , high and ans ; Stores mid ; If A [ mid ] <= num ; Update ans ; Update mid ; Update high ; Driver Code ; Given dimensions of matrix ; Given matrix ; Given number of queries ; Given queries ; Function call to count the number row - sums and column - sums present in the given ranges
import java . io . * ; import java . util . * ; class GFG { static void totalCount ( int [ ] [ ] A , int N , int M , int [ ] [ ] queries , int Q ) { int row_sum [ ] = new int [ N ] ; int col_sum [ ] = new int [ M ] ; 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 < > ( ) ; for ( int i = 0 ; i < N ; i ++ ) sum_list . add ( row_sum [ i ] ) ; for ( int i = 0 ; i < M ; i ++ ) sum_list . add ( col_sum [ i ] ) ; Collections . sort ( sum_list ) ; for ( int i = 0 ; i < Q ; i ++ ) { int L = queries [ i ] [ 0 ] ; int R = queries [ i ] [ 1 ] ; int l = left_search ( sum_list , L ) ; int r = right_search ( sum_list , R ) ; System . out . print ( r - l + 1 + " ▁ " ) ; } } static int left_search ( ArrayList < Integer > A , int num ) { int low = 0 , high = A . size ( ) - 1 ; int ans = 0 ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( A . get ( mid ) >= num ) { ans = mid ; high = mid - 1 ; } else { low = mid + 1 ; } } return ans ; } static int right_search ( ArrayList < Integer > A , int num ) { int low = 0 , high = A . size ( ) - 1 ; int ans = high ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( A . get ( mid ) <= num ) { ans = mid ; low = mid + 1 ; } else { high = mid - 1 ; } } return ans ; } public static void main ( String [ ] args ) { int N = 3 , M = 2 ; int A [ ] [ ] = { { 13 , 3 } , { 9 , 4 } , { 6 , 10 } } ; int Q = 2 ; int queries [ ] [ ] = { { 10 , 20 } , { 25 , 35 } } ; totalCount ( A , N , M , queries , Q ) ; } }