Largest rectangular sub-matrix having sum divisible by k

0 0 17 minutes read

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
Explanation: (Top, Left): (0, 0)
(Bottom, Right): (2, 3)
The sub-matrix is:
| 1, 2, -1, -4 |
| -8, -3, 4, 2 |
| 3, 8, 10, 1 |

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^6).

Algorithm

Initialize variables n, m, and max_area to the number of rows in the matrix, the number of columns in the matrix, and 0, respectively.
Use four nested loops to iterate over all possible sub-matrices in the matrix:
a. The outer two loops iterate over all possible starting positions of the sub-matrix.
b. The inner two loops iterate over all possible ending positions of the sub-matrix.
Use two additional nested loops to calculate the sum of each sub-matrix:
a. The outer loop iterates over each row in the sub-matrix.
b. The inner loop iterates over each column in the sub-matrix.
Check if the sum of the sub-matrix is divisible by k and if the area of the sub-matrix is greater than the current maximum area.
a. If the sum of the sub-matrix is divisible by k and the area of the sub-matrix is greater than the current maximum area, update max_area to the area of the sub-matrix.
Return max_area.

C++

#include <iostream>
#include <vector>
using namespace std;
 
int largest_rectangular_submatrix(vector<vector<int>>& mat, int k) {
    int n = mat.size();
    int m = mat[0].size();
    int max_area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int p = i; p < n; p++) {
                for (int q = j; q < m; q++) {
                    // calculate the sum of the sub-matrix
                    int sum = 0;
                    for (int x = i; x <= p; x++) {
                        for (int y = j; y <= q; y++) {
                            sum += mat[x][y];
                        }
                    }
                    // check if the sum is divisible by k and update max_area if necessary
                    if ((p-i+1)*(q-j+1) > max_area && sum % k == 0) {
                        max_area = (p-i+1)*(q-j+1);
                    }
                }
            }
        }
    }
    return max_area;
}
 
int main() {
    // example usage
    vector<vector<int>> mat = {{1, 2, -1, -4},
                               {-8, -3, 4, 2},
                               {3, 8, 10, 1},
                               {-4, -1, 1, 7}};
    int k = 5;
    int largest_area = largest_rectangular_submatrix(mat, k);
    cout << "Largest area of a sub-matrix whose sum is divisible by " << k << " is " << largest_area << endl;
    return 0;
}

Java

import java.util.*;
 
public class Main {
    public static int largest_rectangular_submatrix(
        ArrayList<ArrayList<Integer> > mat, int k)
    {
        int n = mat.size();
        int m = mat.get(0).size();
        int max_area = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int p = i; p < n; p++) {
                    for (int q = j; q < m; q++) {
                        // calculate the sum of the
                        // sub-matrix
                        int sum = 0;
                        for (int x = i; x <= p; x++) {
                            for (int y = j; y <= q; y++) {
                                sum += mat.get(x).get(y);
                            }
                        }
                        // check if the sum is divisible by
                        // k and update max_area if
                        // necessary
                        if ((p - i + 1) * (q - j + 1)
                                > max_area
                            && sum % k == 0) {
                            max_area
                                = (p - i + 1) * (q - j + 1);
                        }
                    }
                }
            }
        }
        return max_area;
    }
 
    public static void main(String[] args)
    {
        // example usage
        ArrayList<ArrayList<Integer> > mat
            = new ArrayList<>();
        mat.add(
            new ArrayList<>(Arrays.asList(1, 2, -1, -4)));
        mat.add(
            new ArrayList<>(Arrays.asList(-8, -3, 4, 2)));
        mat.add(
            new ArrayList<>(Arrays.asList(3, 8, 10, 1)));
        mat.add(
            new ArrayList<>(Arrays.asList(-4, -1, 1, 7)));
        int k = 5;
        int largest_area
            = largest_rectangular_submatrix(mat, k);
        System.out.println(
            "Largest area of a sub-matrix whose sum is divisible by "
            + k + " is " + largest_area);
    }
}

Python

def largest_rectangular_submatrix(mat, k):
    n = len(mat)
    m = len(mat[0])
    max_area = 0
    for i in range(n):
        for j in range(m):
            for p in range(i, n):
                for q in range(j, m):
                    # calculate the sum of the sub-matrix
                    submat_sum = 0
                    for x in range(i, p+1):
                        for y in range(j, q+1):
                            submat_sum += mat[x][y]
                    # check if the sum is divisible by k and update max_area if necessary
                    if (p-i+1)*(q-j+1) > max_area and submat_sum % k == 0:
                        max_area = (p-i+1)*(q-j+1)
    return max_area
 
# example usage
mat = [[1, 2, -1, -4],
       [-8, -3, 4, 2],
       [3, 8, 10, 1],
       [-4, -1, 1, 7]]
k = 5
largest_area = largest_rectangular_submatrix(mat, k)
print("Largest area of a sub-matrix whose sum is divisible by {} is {}".format(k, largest_area))

C#

using System;
using System.Collections.Generic;
 
class Program {
    static int
    LargestRectangularSubmatrix(List<List<int> > mat, int k)
    {
        int n = mat.Count;
        int m = mat[0].Count;
        int max_area = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int p = i; p < n; p++) {
                    for (int q = j; q < m; q++) {
                        // calculate the sum of the
                        // sub-matrix
                        int sum = 0;
                        for (int x = i; x <= p; x++) {
                            for (int y = j; y <= q; y++) {
                                sum += mat[x][y];
                            }
                        }
                        // check if the sum is divisible by
                        // k and update max_area if
                        // necessary
                        if ((p - i + 1) * (q - j + 1)
                                > max_area
                            && sum % k == 0) {
                            max_area
                                = (p - i + 1) * (q - j + 1);
                        }
                    }
                }
            }
        }
        return max_area;
    }
 
    static void Main(string[] args)
    {
        // example usage
        List<List<int> > mat = new List<List<int> >{
            new List<int>{ 1, 2, -1, -4 },
            new List<int>{ -8, -3, 4, 2 },
            new List<int>{ 3, 8, 10, 1 },
            new List<int>{ -4, -1, 1, 7 }
        };
        int k = 5;
        int largest_area
            = LargestRectangularSubmatrix(mat, k);
        Console.WriteLine(
            "Largest area of a sub-matrix whose sum is divisible by "
            + k + " is " + largest_area);
    }
}

Javascript

// JavaScript implementation to find largest rectangular
// sub-matrix having sum divisible by k
// function to find the longest subarray with sum divisible
// by k.
function largestRectangularSubmatrix(mat, k) {
  var n = mat.length;
  var m = mat[0].length;
  var maxArea = 0;
   
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < m; j++) {
      for (var p = i; p < n; p++) {
        for (var q = j; q < m; q++) {
          // calculate the sum of the sub-matrix
          var sum = 0;
          for (var x = i; x <= p; x++) {
            for (var y = j; y <= q; y++) {
              sum += mat[x][y];
            }
          }
           
          // check if the sum is divisible by k and 
          // update maxArea if necessary
          if ((p - i + 1) * (q - j + 1) > maxArea && sum % k === 0) {
            maxArea = (p - i + 1) * (q - j + 1);
          }
        }
      }
    }
  }
   
  return maxArea;
}
 
// Driver code
var mat = [[1, 2, -1, -4],
           [-8, -3, 4, 2],
           [3, 8, 10, 1],
           [-4, -1, 1, 7]];
var k = 5;
var largestArea = largestRectangularSubmatrix(mat, k);
console.log("Largest area of a sub-matrix whose sum is divisible by " + k + " is " + largestArea);

Output

Largest area of a sub-matrix whose sum is divisible by 5 is 12

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.

Implementation:

C++

// C++ implementation to find largest rectangular
// sub-matrix having sum divisible by k
#include <bits/stdc++.h>
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)
{
    // unordered 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 << ")\n";
    cout << "(Bottom, Right): (" << finalBottom << ", "
         << finalRight << ")\n";
    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;
}

Java

// Java implementation to find largest 
// rectangular sub-matrix having sum 
// divisible by k
import java.util.*;
 
class GFG{
 
static final int SIZE = 10;
static int start, finish;
 
// 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
static void longSubarrWthSumDivByK(int arr[], 
                                   int n, int k)
{
     
    // unordered map 'um' implemented as
    // hash table
    HashMap<Integer, Integer> um = new HashMap<>();
 
    // 'mod_arr[i]' stores (sum[0..i] % k)
    int []mod_arr = new int[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.containsKey(mod_arr[i]))
            um.put(mod_arr[i], i);
 
        else
         
            // If true, then update variables
            if (max < (i - um.get(mod_arr[i])))
            {
                max = i - um.get(mod_arr[i]);
                start = um.get(mod_arr[i]) + 1;
                finish = i;
            }
    }
}
 
// Function to find largest rectangular 
// sub-matrix having sum divisible by k
static void findLargestSubmatrix(int mat[][], 
                                 int n, int k)
{
     
    // Variables to store the final output
    int finalLeft = 0, finalRight = 0, 
        finalTop = 0, finalBottom = 0;
 
    int left, right, i, maxArea = 0;
    int []temp = new int[n];
 
    // Set the left column
    for(left = 0; left < n; left++)
    {
         
        // Initialize all elements of temp as 0
        Arrays.fill(temp, 0);
 
        // 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);
 
            // 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
    System.out.print("(Top, Left): (" +
                     finalTop + ", " + 
                     finalLeft + ")\n");
    System.out.print("(Bottom, Right): (" + 
                     finalBottom + ", " + 
                     finalRight + ")\n");
    System.out.print("Area: " + maxArea);
}
 
// Driver code
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);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python implementation to find largest rectangular
# sub-matrix having sum divisible by k
 
start = 0
finish = 0
 
# 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.
def longSubarrWthSumDivByK(arr, n, k):
 
    # unordered map 'um' implemented as
    # hash table
 
    global start,finish
 
    um = {}
 
    # 'mod_arr[i]' stores (sum[0..i] % k)
    mod_arr = [0 for i in range(n)]
    curr_sum,Max = 0,0
 
    # traverse arr[] and build up the
    # array 'mod_arr[]'
    for i in range(n):
        curr_sum += arr[i]
 
        # as the sum can be negative, taking modulo twice
        mod_arr[i] = ((curr_sum % k) + k) % k
 
    for i in range(n):
 
        # 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
        elif (mod_arr[i] not in um):
            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
def findLargestSubmatrix(mat, n, k):
    # Variables to store the final output
    finalLeft, finalRight, finalTop, finalBottom = 0,0,0,0
 
    left, right, i, maxArea = 0,0,0,0
    temp = [0 for i in range(n)]
 
    # Set the left column
    for left in range(n):
 
        # Set the right column for the left column
        # set by outer loop
        for right in range(left,n):
 
            # Calculate sum between current left and 
            # right for every row 'i'
            for i in range(n):
                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)
 
            # 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
    print(f"(Top, Left): ({finalTop}, {finalLeft})")
    print(f"(Bottom, Right): ({finalBottom}, {finalRight})")
    print(f"Area: {maxArea}")
 
# Driver program to test above functions
 
mat = [ [ 1, 2, -1, -4 ],
        [ -8, -3, 4, 2 ],
        [ 3, 8, 10, 1 ],
        [ -4, -1, 1, 7 ] ]
 
n,k = 4,5
findLargestSubmatrix(mat, n, k)
 
# code is contributed by shinjanpatra

C#

// C# implementation to find largest 
// rectangular sub-matrix having sum 
// divisible by k
using System;
using System.Collections.Generic;
 
class GFG{
 
//static readonly int SIZE = 10;
static int start, finish;
 
// 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
static void longSubarrWthSumDivByK(int []arr, 
                                   int n, int k)
{
     
    // unordered map 'um' implemented as
    // hash table
    Dictionary<int, 
               int> um = new Dictionary<int,
                                        int>();
 
    // 'mod_arr[i]' stores (sum[0..i] % k)
    int []mod_arr = new int[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.ContainsKey(mod_arr[i]))
            um.Add(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
static void findLargestSubmatrix(int [,]mat, 
                                 int n, int k)
{
     
    // Variables to store the readonly output
    int finalLeft = 0, finalRight = 0, 
        finalTop = 0, finalBottom = 0;
 
    int left, right, i, maxArea = 0;
    int []temp;
 
    // Set the left column
    for(left = 0; left < n; left++)
    {
         
        // Initialize all elements of temp as 0
        temp = new int[n];
 
        // 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);
 
            // 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 readonly values
    Console.Write("(Top, Left): (" +
                   finalTop + ", " + 
                  finalLeft + ")\n");
    Console.Write("(Bottom, Right): (" + 
                    finalBottom + ", " + 
                     finalRight + ")\n");
    Console.Write("Area: " + maxArea);
}
 
// Driver code
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);
}
}
 
// This code is contributed by Princi Singh

Javascript

// JS implementation to find largest rectangular
// sub-matrix having sum divisible by k
 
let 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.
function longSubarrWthSumDivByK(arr, n, k, start, finish)
{
    // unordered map 'um' implemented as
    // hash table
    let um = {};
 
    // 'mod_arr[i]' stores (sum[0..i] % k)
    let mod_arr = new Array(n);
    let curr_sum = 0, max = 0;
 
    // traverse arr[] and build up the
    // array 'mod_arr[]'
    for (let 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 (let 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.hasOwnProperty(mod_arr[i]))
            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
function findLargestSubmatrix(mat, n, k)
{
    // Variables to store the final output
    let finalLeft = 0, finalRight = 0, finalTop = 0, finalBottom = 0;
 
    let left = 0, right = 0, i = 0, maxArea = 0;
    let start = 0, finish = 0, temp
 
    // Set the left column
    for (left = 0; left < n; left++) {
 
        // Initialize all elements of temp as 0
        temp = new Array(n).fill(0)
 
        // 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
    console.log("(Top, Left): (" + finalTop + ", "
         + finalLeft + ")");
    console.log("(Bottom, Right): (" + finalBottom + ", "
         + finalRight + ")");
    console.log("Area: " + maxArea);
}
 
// Driver program to test above functions
let mat = [[ 1, 2, -1, -4 ], [-8, -3, 4, 2], [ 3, 8, 10, 1 ], [-4, -1, 1, 7 ]];
 
    let n = 4, k = 5;
    findLargestSubmatrix(mat, n, k);
 
// This code is contributed by phasing17.

Output

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

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!