Largest rectangular sub matrix having sum divisible by k
Sign up for FREE 1 month of Kindle and read all our books for free.
Get FREE domain for 1st year and build your brand new site
Reading time: 35 minutes  Coding time: 10 minutes
You are given a N X N matrix consisting of some integral values in each cell.The task is to find the largest area of a rectangular submatrix such that the total sum of all the elements in that area of the submatrix is divisible by a number k.
For example if our 4 X 4 matrix is:
and if the value of k = 2.
In this case the largest area of a rectangular submatrix having sum divisible by 2 is:
So basically we have found a submatrix(the one highlighted in blue)which has the maximum area of 9(3 * 3).The submatrix has the top left corner at (1,0) and the bottom right corner at (3,2).The total sum of all the elements of the submatrix is 14 (2+623+5+6+4+22), which is divisible by 2(which is the value of k in this case).
Input format
We have to input the value of N (4 in the above example), also we will have to input the value of k (2 in above example).The matrix will also be taken as the input.
Output format
Maximum area: 9
Coordinate of top leftcorner: (1,0)
Coordinate of bottomright corner: (3,2)
Method:
We will solve the problem by applying the Dynamic Programming approach.
Step 1: One by one we will fix the left and right index for all the possible column in the matrix. For eg: If our N=5 then we will check for index pairs: [ (0,0) (0,1) (0,2) (0,3) (1,1) (1,2) (1,3) .....(3,3) (3,4) (4,4) ]. Now for each left and right column pair we will find the top and bottom indexes of the row such that the sum of the elements in that particular area is divisible by k.
Step 2: For finding the top and bottom indexes of the row we will compute the sum of the elements of each row starting from the left column index and ending at the right column index. After this we will store the sum of every ith row in a temporary array, sum[]; so basically the sum[i] will denote the sum of the elements from left to right for ith row.
Step 3: After this we will apply an algorithm on the sum[] array such that it will find the longest subarray having the sum divisible by k.
Step 4: Whenever we get a subarray of a sum divisible by k then we will update the value of the maxArea (if maxArea< current area) and also the left and right column indexes, and top and bottom row indexes.
Pseudocode:
START
1. Consider all the left and right indexes for every column pair.
2. Store the sum of every row within the left and right indexes in sum[].
3. Follow the steps to find the longest subarray for sum[] which has sum of elements divisible by k.
4. Create a mod[] array where mod[i] stores [(sum[0]+sum[1]...sum[i])%k].
5. Create a map which maps element of mod[] to the element's index of first occurence in mod[].
6. Linearly traverse mod[] from 0 to n and check the following conditions.
7. If mod[i]==0 then update lenMax=(i+1).
8. Else if mod[i] is not present in our map then map mod[i] to i.
9. Else take the value which is mapped for mod[i] and check if lenMax<(ivalue).If it is true then update lenMax=(ivalue).
END
Implementation in C++:
#include<bits/stdc++.h>
using namespace std;
#define MAX 100
vector<int>LongestSubarrayDivSumK(int sum[], int n, int k);
void LargestRectangle(int mat[MAX][MAX], int n, int k)
{
//Initializing all the variables
int AreaMaximum= 0;
int left,right,i;
int LeftIndex,RightIndex,TopIndex,BottomIndex;
int sum[n];
// vector gives the top and bottom indexes of the rows
vector<int>startAndFinish;
//the start for the left column index
for(left=0; left<n; left++)
{
//Assigning all the values of sum[] to 0
for(i=0;i<n;i++)
sum[i]=0;
//end of the column index
for(right=left; right<n; right++)
{
//calculating the sum for every row
for(i=0;i<n;i++)
{
sum[i]=sum[i]+ mat[i][right];
}
//getting the top and bottom value in startAndFinish vector
startAndFinish= LongestSubarrayDivSumK(sum , n , k);
//the first element of the startAndFinish vector is the TopIndex
//the second element of the startAndFinish vector is the BottomIndex
//Checking for the maximum area
if (AreaMaximum < ((right  left + 1) * (startAndFinish[1] startAndFinish[0] + 1)))
{
LeftIndex = left; RightIndex = right;
TopIndex = startAndFinish[0]; BottomIndex = startAndFinish[1];
AreaMaximum = (right  left + 1) * (startAndFinish[1]  startAndFinish[0] + 1);
}
}
}
//Printing the results
cout<<"Maximum Area : "<<AreaMaximum<<endl;
cout<<"Topleft corner : "<<"( "<<TopIndex<<" , ";
cout<<LeftIndex<<" )"<<endl;
cout<<"Bottomright corner : "<<"( "<<BottomIndex<<" , ";
cout<<RightIndex<<" ) ";
}
vector<int>LongestSubarrayDivSumK(int sum[], int n, int k)
{
int mod[n];
vector<int>StartAndFinish(2);
int presentSum=0;
int LenMax=0;
map<int, int>mp;
int i,j;
//Calculating the value for mod[i] based on the current sum
for(i=0;i<n;i++)
{
presentSum=presentSum+sum[i];
//assigning values to mod[]
mod[i]=presentSum % k;
//for handling negative values
mod[i]=(mod[i]+k)%k;
}
//Checking the conditions for longest subarray
for(i=0;i<n;i++)
{
//if the length is starting from 0 then it has to be max
if(mod[i]==0)
{
StartAndFinish[0]=0;
StartAndFinish[1]=i;
LenMax=i+1;
}
//if mod[i] is present in our map
else if(mp.find(mod[i])!= mp.end())
{
//Checking the max length so far
if(LenMax < (imp[mod[i]]))
{
StartAndFinish[0]=mp[mod[i]]+1;
StartAndFinish[1]=i;
LenMax=imp[mod[i]];
}
}
//if mod[i] is not present in our map
else
{
mp[mod[i]]=i;
}
}
return StartAndFinish;
}
int main()
{
cout<<"Enter the value for N: "<<endl;
int N;
cin>>N;
cout<<"Enter the value for k : "<<endl;
int k;
cin>>k;
cout<<"Enter your N X N matrix :"<<endl;
int i,j;
int mat[MAX][MAX];
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
cin>>mat[i][j];
}
}
LargestRectangle(mat, N, k);
return 0;
}
Explanation with an example:
For eg if for N=3 and k=2 our matrix is:
So one by one we will consider left and right column indexes :(0,0) (0,1) (0,2) (1,1) (1,2) (2,2)
When we will calculate the sum[] array for (0,2) indexes:
sum[]={8, 1, 1}
So when we apply the above algorithmn to find the longest subarray in sum[] array, we find out that the the complete array itself is the longest subarray having sum divisible by 2(value of k in this case).
Hence we arrive on the conclusion that the largest rectangular sub matrix having sum divisible by k is:
Maximum Area : 9
Topleft corner : ( 0 , 0 )
Bottomright corner : ( 2 , 2 )
Complexity Analysis:
Time complexity: O(n^3)
Space complexity (Auxillary Space): O(n)
Applications:

The above code can be used to find the maximum area of the rectangular submatrix such that the sum of the elements is divisible by k.

With a little modification in the code we can also find all the possible rectangular submatrix with the largest area and having the sum of the elements divisible by k.
Question
You are given a N X N matrix and you have to find out the largest area of rectangular submatrix such that the sum of all the elements in that submatrix is divisible by an integer k.
Input:
Enter the value for N: .........
Enter the value for k: .........
Enter your N X N matrix: .........
Output:
Maximum Area:........
Topleft corner:.......
Bottomright corner:.......