Home » Technical Interview Questions » Dynamic Programming Interview Questions » Largest rectangular sub-matrix whose sum is 0

Largest rectangular sub-matrix whose sum is 0


Problem Statement

Find the maximum size sub-matrix in a 2D array whose sum is zero. A sub-matrix is nothing but a 2D array inside of the given 2D array. So, you have a matrix of signed integers, you need to calculate the sum of sub-matrices and find the matrix with maximum size whose sum is zero.

Example

Largest rectangular sub-matrix whose sum is 0

Matrix = { 0      10      0
         -20      10    100
          10    -100    -10 }
9

Explanation: Here, in this given input we have only one possible answer. We can choose a sub-matrix of size 9(whole matrix) which will be the maximum size sub-matrix. So, we shall choose entire matrix as the answer.

Matrix = { 100
          -100
           100 }
2

Explanation: There are two options to choose from. Either you choose first and second row or second and third row. Both of them will result into sum = 0.

Approach to find largest rectangular sub-matrix whose sum is 0

Naive Approach

We can take care of this issue by utilizing a simple arrangement. We can utilize four indices each for various cells of the matrix. Out of these indices, one will be for a beginning row, beginning column, finishing row, and finishing column. We can utilize a 2D prefix sum approach for slightly improving our solution. This methodology can optimize our simple solution a little yet that won’t be enough, however.

Efficient Approach

So, we will use a similar approach as we did with the problem Find sub-matrix with maximum Sum. We will now fix two columns, one for the left column and one for the right column. For storing the sums between these columns for each of the rows from starting 0th row to the end row (n-1th), we will create a temporary array. Now, we will make use of map data structure for storing the indices for sums encountered until now.

READ  Longest Repeated Subsequence

Just to get a hang of this approach, you can consider a 1D array of prefix sums, and if we find two same values in the prefix sum array. That means we have two indices until which the sum of elements is the same. So, if we subtract the sum at a smaller index from the sum at a higher index. We get the sum between the smaller index and the higher index. Since both of those values were equal. We are left with sum = 0. The same thing is what we are doing here.

Code for finding the largest rectangular sub-matrix whose sum is 0

C++ Code

#include<bits/stdc++.h>
using namespace std;

int findMaximumSubMatrixWithZeroSum(vector<vector<int>> matrix, int n, int m){
    // stores the prefixSum of rows
    vector<vector<int>> prefixSum(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            prefixSum[i][j] = matrix[i][j];
    }

    // calculation prefix sum for each row
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++)
            prefixSum[i][j] += prefixSum[i][j-1];
    }

    // store indices of submatrix with maximum sum
    int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
    int maxSize = 0;
    // use a map to first store the row for sum if it was not present earlier
    // else we calculate the result regarding the particular sum
    for(int firstCol=0;firstCol<m;firstCol++){
        for(int secondCol=firstCol;secondCol<m;secondCol++){
            int tmp[n]; // stores the sum between two columns for each row
            for(int row=0;row<n;row++)
                tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);

            int curSum = 0;
            unordered_map<int,int> rowSumMap;
            rowSumMap[0] = -1;
            for(int curRow=0;curRow<n;curRow++){
                curSum += tmp[curRow];
                if(rowSumMap.count(curSum)) {
                    int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap[curSum]);
                    if(subMatrixSize > maxSize){
                        maxSize = subMatrixSize;
                        startCol = firstCol;
                        endCol = secondCol;
                        startRow = rowSumMap[curSum] + 1;
                        endRow = curRow;
                    }
                } else {
                    rowSumMap[curSum] = curRow;
                }
            }
        }
    }
    
    if(maxSize == 0){
        cout<<"There exists no sub-matrix with zero sum"<<endl;
        return 0;
    }
    cout<<"Sub-matrix with zero Sum"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    return maxSize;
}

int main(){
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<vector<int>> matrix(n,vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                cin>>matrix[i][j];
        }
        int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
        if(ans != 0)
        cout<<ans<<endl;
    }
}

 

2
4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0 -9
 1  8  8   4

4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0  9
 1  8  8   4

Largest Sub-matrix with zero Sum 
5 9 8 7 
-9 -5 -4 -2 
0 0 0 -9 
12
Largest Sub-matrix with zero Sum 
5 9 
-9 -5 
0 0 
6

 

READ  Tiling Problem

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int findMaximumSubMatrixWithZeroSum(int[][] matrix, int n, int m){
        // stores the prefixSum of rows
        int[][] prefixSum = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                prefixSum[i][j] = matrix[i][j];
        }
    
        // calculation prefix sum for each row
        for(int i=0;i<n;i++){
            for(int j=1;j<m;j++)
                prefixSum[i][j] += prefixSum[i][j-1];
        }
    
        int startCol = 0, endCol = 0, startRow = 0, endRow = 0;
        int maxSize = 0;
        for(int firstCol=0;firstCol<m;firstCol++){
            for(int secondCol=firstCol;secondCol<m;secondCol++){
                int tmp[] = new int[n]; // stores the sum between two columns for each row
                for(int row=0;row<n;row++)
                    tmp[row] = prefixSum[row][secondCol] - (firstCol>0 ? prefixSum[row][firstCol-1] : 0);
                
                int curSum = 0;
                HashMap<Integer, Integer> rowSumMap = new HashMap<Integer, Integer>();
                rowSumMap.put(0,-1);
                for(int curRow=0;curRow<n;curRow++){
                    curSum += tmp[curRow];
                    if(rowSumMap.containsKey(curSum)) {
                        int subMatrixSize = (secondCol - firstCol + 1)*(curRow - rowSumMap.get(curSum));
                        if(subMatrixSize > maxSize){
                            maxSize = subMatrixSize;
                            startCol = firstCol;
                            endCol = secondCol;
                            startRow = rowSumMap.get(curSum) + 1;
                            endRow = curRow;
                        }
                    } else {
                        rowSumMap.put(curSum,curRow);
                    }
                }
            }
        }
        
        if(maxSize == 0){
            System.out.println("There exists no sub-matrix with zero sum");
            return 0;
        }
        System.out.println("Largest Sub-matrix with zero Sum");
        for(int i=startRow;i<=endRow;i++){
            for(int j=startCol;j<=endCol;j++){
                System.out.print(matrix[i][j]+" ");
            }
            System.out.println();
        }
        return maxSize;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int matrix[][] = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++)
                    matrix[i][j] = sc.nextInt();
            }
            int ans = findMaximumSubMatrixWithZeroSum(matrix, n, m);
            if(ans != 0)
            System.out.println(ans);
        }
    }
}
2
4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0 -9
 1  8  8   4

4 4
 5  9  8  7 
-9 -5 -4 -2
 0  0   0  9
 1  8  8   4

Largest Sub-matrix with zero Sum 
5 9 8 7 
-9 -5 -4 -2 
0 0 0 -9 
12
Largest Sub-matrix with zero Sum 
5 9 
-9 -5 
0 0 
6

 

Complexity Analysis

Time Complexity: O(N^3)

We have a polynomial-time complexity of O(N^3) because there are three nested loops. One loop is used for finding the zero Sum using prefix Sum and map technique.

Space Complexity: O(N^2)

Since we made a 2D prefix Sum array. We have space complexity of O(N^2).

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup