PRINT LARGEST SUBMATRIX WITH SUM ZERO | HARD | OA

https://practice.geeksforgeeks.org/problems/largest-rectangular-sub-matrix-whose-sum-is-0/1?page=1&difficulty[]=1&difficulty[]=2&status[]=unsolved&category[]=Dynamic%20Programming&category[]=Binary%20Search&category[]=Trie&category[]=union-find&sortBy=submissions

Given a matrix mat[][] of size N x M. The task is to find the largest rectangular sub-matrix by area whose sum is 0.

If there are multiple solutions return the rectangle which starts from minimum column index. If you still have multiple solutions return the one starting from minimum row index. If you still have multiple solutions return the one having greatest row number. If no such matrix is present return a zero (0) size matrix.

Example 1:
Input: N = 3, M = 3
mat[][] =  1, 2, 3
          -3,-2,-1
           1, 7, 5
Output:  1, 2, 3
        -3,-2,-1

Example 2:
Input: N = 4, M = 4
mat[][] = 9, 7, 16, 5
          1,-6,-7, 3
          1, 8, 7, 9
          7, -2, 0, 10

Output: -6,-7
          8, 7
         -2, 0
---------------------------------------------------------------------------------------------------------------------------------------


Code explanation-

You may be wondering, why I am not taking into considering other tie breaking conditions. Let us understand
I am iterating from r1=0 to r2=n. So, if I find an maxanswer that was seen before. I am sure that maxanswer will have minimum row index.

The reason we are using column as tie breaker is because it is what matters now. row index and row number are already taken care of. Actually if you think, YOU WILL REALISE THIS ROW NUMBER CONDITION DOES NOT EVEN MATTER HERE. So the answer now depends only on column, cuz the current answer if equal to already max answer, would fail at second condition cuz max that occurred before had minimum row index.

---------------------------------------------------------------------------------------------------------------------------------------

class Solution{
  public:
  pair<int,int> getCoordinates(vector<int> &arr){
      unordered_map<int,int> mpp;
      int currsum=0;
      int mxLength=0;
      pair<int,int> res={-1,-1};
      for(int i=0;i<arr.size();i++){
          currsum+=arr[i];
          if(currsum==0){
              mxLength=i+1;
              res={0,i};
          }
          if(mpp.find(currsum)!=mpp.end()){
              if(mxLength<i-mpp[currsum]){
                  mxLength=i-mpp[currsum];
                  res={mpp[currsum]+1,i};
              }
          }
          else{
              mpp[currsum]=i; /* because we do not want to
                                 update with greater index
                                 for same sum. Doing this will
                                 give us a higher probability
                                 of getting larger lengths */
          }
      }
      return res;
  }

  vector<vector<int>> sumZeroMatrix(vector<vector<int>> a){
      int mxSum=0;
      int n=a.size();
      int m=a[0].size();

      int r1=INT_MAX;
      int c1=INT_MAX;
      int r2=INT_MAX;
      int c2=INT_MAX;

      for(int i=0;i<n;i++){
          vector<int> sum(m,0);
          for(int j=i;j<n;j++){
              for(int k=0;k<m;k++){
                  sum[k]+=a[j][k];
              }
              auto cood=getCoordinates(sum);

              if(cood.first==-1){  // did not get zero sum rectangle
                  continue;
              }

              int Tr1=i;
              int Tr2=j;
              int Tc1=cood.first;
              int Tc2=cood.second;
              int size=(Tr2-Tr1+1)*(Tc2-Tc1+1);

              if(size>mxSum || (size==mxSum && Tc1<c1)){
                  mxSum=size;
                  r1=Tr1;
                  r2=Tr2;
                  c1=Tc1;
                  c2=Tc2;
              }
          }
      }
      vector<vector<int>> res;

      if(r1==INT_MAX){ // no answer found
          return res;
      }

      for(int i=r1;i<=r2;i++){
          vector<int> temp;
          for(int j=c1;j<=c2;j++){
              temp.push_back(a[i][j]);
          }
          res.push_back(temp);
      }

      return res;
  }