Largest rectangular sub | Java implementation to find largest rectangular sub - matrix having sum divisible by k ; static readonly int SIZE = 10 ; ; Function to find the longest subarray with sum divisible by k . The function stores starting and ending indexes of the subarray at addresses pointed by start and finish pointers respectively ; unordered map ' um ' implemented as hash table ; ' mod _ arr [ i ] ' stores ( sum [ 0. . i ] % k ) ; Traverse arr [ ] and build up the array ' mod _ arr [ ] ' ; As the sum can be negative , taking modulo twice ; If true then sum ( 0. . i ) is divisible by k ; Update variables ; If value ' mod _ arr [ i ] ' not present in ' um ' then store it in ' um ' with index of its first occurrence ; If true , then update variables ; Function to find largest rectangular sub - matrix having sum divisible by k ; Variables to store the final output ; Set the left column ; Initialize all elements of temp as 0 ; Set the right column for the left column set by outer loop ; Calculate sum between current left and right for every row ' i ' ; The longSubarrWthSumDivByK ( ) function sets the values of ' start ' and ' finish ' . So submatrix having sum divisible by ' k ' between ( start , left ) and ( finish , right ) which is the largest submatrix with boundary columns strictly as left and right . ; Calculate current area and compare it with maximum area so far . If maxArea is less , then update maxArea and other output values ; Print final values ; Driver code
import java . util . * ; class GFG { static final int SIZE = 10 ; static int start , finish ; static void longSubarrWthSumDivByK ( int arr [ ] , int n , int k ) { HashMap < Integer , Integer > um = new HashMap < > ( ) ; int [ ] mod_arr = new int [ n ] ; int curr_sum = 0 , max = 0 ; for ( int i = 0 ; i < n ; i ++ ) { curr_sum += arr [ i ] ; mod_arr [ i ] = ( ( curr_sum % k ) + k ) % k ; } for ( int i = 0 ; i < n ; i ++ ) { if ( mod_arr [ i ] == 0 ) { max = i + 1 ; start = 0 ; finish = i ; } else if ( ! um . containsKey ( mod_arr [ i ] ) ) um . put ( mod_arr [ i ] , i ) ; else if ( max < ( i - um . get ( mod_arr [ i ] ) ) ) { max = i - um . get ( mod_arr [ i ] ) ; start = um . get ( mod_arr [ i ] ) + 1 ; finish = i ; } } } static void findLargestSubmatrix ( int mat [ ] [ ] , int n , int k ) { int finalLeft = 0 , finalRight = 0 , finalTop = 0 , finalBottom = 0 ; int left , right , i , maxArea = 0 ; int [ ] temp = new int [ n ] ; for ( left = 0 ; left < n ; left ++ ) { Arrays . fill ( temp , 0 ) ; for ( right = left ; right < n ; right ++ ) { for ( i = 0 ; i < n ; ++ i ) temp [ i ] += mat [ i ] [ right ] ; longSubarrWthSumDivByK ( temp , n , k ) ; if ( maxArea < ( ( right - left + 1 ) * ( finish - start + 1 ) ) ) { finalLeft = left ; finalRight = right ; finalTop = start ; finalBottom = finish ; maxArea = ( right - left + 1 ) * ( finish - start + 1 ) ; } } } System . out . print ( " ( Top , ▁ Left ) : ▁ ( " + finalTop + " , ▁ " + finalLeft + ")NEW_LINE"); System . out . print ( " ( Bottom , ▁ Right ) : ▁ ( " + finalBottom + " , ▁ " + finalRight + ")NEW_LINE"); System . out . print ( " Area : ▁ " + maxArea ) ; } public static void main ( String [ ] args ) { int [ ] [ ] mat = { { 1 , 2 , - 1 , - 4 } , { - 8 , - 3 , 4 , 2 } , { 3 , 8 , 10 , 1 } , { - 4 , - 1 , 1 , 7 } } ; int n = 4 , k = 5 ; findLargestSubmatrix ( mat , n , k ) ; } }