# Largest rectangular sub-matrix having sum divisible by k

Given a n x n matrix of integers. The problem is to find the largest area rectangular sub-matrix having sum divisible by the given value k.

Examples:

```Input : mat[][] = { {1, 2, -1, -4},
{-8, -3, 4, 2},
{3, 8, 10, 1},
{-4, -1, 1, 7} }

k = 5

Output : Area = 12
(Top, Left): (0, 0)
(Bottom, Right): (2, 3)
The sub-matrix is:
| 1, 2, -1, -4 |
| -8, -3, 4, 2 |
| 3, 8, 10, 1  |
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive Approach: Check every possible rectangle in given 2D array having sum divisible by ‘k’ and print the largest one. This solution requires 4 nested loops and time complexity of this solution would be O(n^4).

Efficient Approach: Longest subarray having sum divisible by k for 1-D array can be used to reduce the time complexity to O(n^3). The idea is to fix the left and right columns one by one and find the longest sub-array having sum divisible by ‘k’ for contiguous rows for every left and right column pair. We basically find top and bottom row numbers (which are part of the largest sub-matrix) for every fixed left and right column pair. To find the top and bottom row numbers, calculate sum of elements in every row from left to right and store these sums in an array say temp[]. So temp[i] indicates sum of elements from left to right in row i. Now, apply Longest subarray having sum divisible by k 1D algorithm on temp[], and get the longest sub-array having sum divisible by ‘k’ of temp[]. This length would be the maximum possible length with left and right as boundary columns. Set the ‘top’ and ‘bottom’ row indexes for the left right column pair and calculate the area. In similar manner get the top, bottom, left, right indexes for other sub-matrices having sum divisible by ‘k’ and print the one having maximum area.

 `// C++ implementation to find largest rectangular ` `// sub-matrix having sum divisible by k ` `#include ` `using` `namespace` `std; ` ` `  `#define 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. ` `void` `longSubarrWthSumDivByK(``int` `arr[], ``int` `n, ``int` `k, ` `                            ``int``& start, ``int``& finish) ` `{ ` `    ``// unodered map 'um' implemented as ` `    ``// hash table ` `    ``unordered_map<``int``, ``int``> um; ` ` `  `    ``// 'mod_arr[i]' stores (sum[0..i] % k) ` `    ``int` `mod_arr[n]; ` `    ``int` `curr_sum = 0, max = 0; ` ` `  `    ``// traverse arr[] and build up the ` `    ``// array 'mod_arr[]' ` `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``curr_sum += arr[i]; ` ` `  `        ``// as the sum can be negative, taking modulo twice ` `        ``mod_arr[i] = ((curr_sum % k) + k) % k; ` `    ``} ` ` `  `    ``for` `(``int` `i = 0; i < n; i++) { ` ` `  `        ``// if true then sum(0..i) is divisible ` `        ``// by k ` `        ``if` `(mod_arr[i] == 0) { ` ` `  `            ``// update variables ` `            ``max = i + 1; ` `            ``start = 0; ` `            ``finish = i; ` `        ``} ` ` `  `        ``// if value 'mod_arr[i]' not present in 'um' ` `        ``// then store it in 'um' with index of its ` `        ``// first occurrence ` `        ``else` `if` `(um.find(mod_arr[i]) == um.end()) ` `            ``um[mod_arr[i]] = i; ` ` `  `        ``else` `            ``// if true, then update variables ` `            ``if` `(max < (i - um[mod_arr[i]])) { ` `            ``max = i - um[mod_arr[i]]; ` `            ``start = um[mod_arr[i]] + 1; ` `            ``finish = i; ` `        ``} ` `    ``} ` `} ` ` `  `// function to find largest rectangular sub-matrix ` `// having sum divisible by k ` `void` `findLargestSubmatrix(``int` `mat[SIZE][SIZE], ``int` `n, ``int` `k) ` `{ ` `    ``// Variables to store the final output ` `    ``int` `finalLeft, finalRight, finalTop, finalBottom; ` ` `  `    ``int` `left, right, i, maxArea = 0; ` `    ``int` `temp[n], start, finish; ` ` `  `    ``// Set the left column ` `    ``for` `(left = 0; left < n; left++) { ` ` `  `        ``// Initialize all elements of temp as 0 ` `        ``memset``(temp, 0, ``sizeof``(temp)); ` ` `  `        ``// Set the right column for the left column ` `        ``// set by outer loop ` `        ``for` `(right = left; right < n; right++) { ` ` `  `            ``// Calculate sum between current left and  ` `            ``// right for every row 'i' ` `            ``for` `(i = 0; i < n; ++i) ` `                ``temp[i] += mat[i][right]; ` ` `  `            ``// 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. ` `            ``longSubarrWthSumDivByK(temp, n, k, start, finish); ` ` `  `            ``// Calculate current area and compare it with  ` `            ``// maximum area so far. If maxArea is less, then  ` `            ``// update maxArea and other output values ` `            ``if` `(maxArea < ((right - left + 1) *  ` `                          ``(finish - start + 1))) { ` `                ``finalLeft = left; ` `                ``finalRight = right; ` `                ``finalTop = start; ` `                ``finalBottom = finish; ` `                ``maxArea = (right - left + 1) * (finish - start + 1); ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Print final values ` `    ``cout << ``"(Top, Left): ("` `<< finalTop << ``", "` `         ``<< finalLeft << ````") "````; ` `    ``cout << ``"(Bottom, Right): ("` `<< finalBottom << ``", "` `         ``<< finalRight << ````") "````; ` `    ``cout << ``"Area: "` `<< maxArea; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``int` `mat[SIZE][SIZE] = { { 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); ` ` `  `    ``return` `0; ` `} `

Output:

```(Top, Left): (0, 0)
(Bottom, Right): (2, 3)
Area: 12
```

Time Complexity: O(n^3).
Auxiliary Space: O(n).