# Largest rectangular sub matrix having sum divisible by k

#### Algorithms Dynamic Programming (DP)

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 sub-matrix 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 sub-matrix 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+6-2-3+5+6+4+2-2), 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
Co-ordinate of top left-corner: (1,0)
Co-ordinate of bottom-right 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<(i-value).If it is true then update lenMax=(i-value).
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<<"Top-left corner : "<<"( "<<TopIndex<<" , ";
cout<<LeftIndex<<" )"<<endl;
cout<<"Bottom-right 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 < (i-mp[mod[i]]))
{
StartAndFinish[0]=mp[mod[i]]+1;
StartAndFinish[1]=i;
LenMax=i-mp[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
Top-left corner : ( 0 , 0 )
Bottom-right corner : ( 2 , 2 )

## Complexity Analysis:

Time complexity: O(n^3)
Space complexity (Auxillary Space): O(n)

## Applications:

1. 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.

2. 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:........
Top-left corner:.......
Bottom-right corner:.......