1 جي ۽ 0 جي برابر تعداد سان گڏ سڀني کان وڏي علائقي جي مستطيل ذيلي ميٽرڪس


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Accenture يقينا انفارميشن ايج مونوٽائپ حل PayPal Pinterest ڪنڊوزس ٽائمز انٽرنيٽ UHG آپٽم
ڪيريو متحرڪ پروگرامنگ قائم ٿينديون

مسئلي جو بيان

ھڪڙي سائز جو بائنري ميٽرڪس ڏنو ويو آھي ايڪس ايم ايم. مسئلو 1 ۽ 0 جي برابر تعداد سان گڏ سڀ کان وڏو علائقو مستطيل ذيلي ميٽرڪس ڳولڻ آهي.

مثال

Dimensions = 4 x 4
Matrix:
1 1 1 1
0 1 0 1
1 0 1 0
1 0 0 0
12

وضاحت: جيڪڏهن اسان ذيلي ذخيرو کي ڪنارن سان سمجهون ٿا (0,1،0,3) ، (3,1،3,3) ، (0،1) ۽ (XNUMX،XNUMX). هي ذيلي ميٽرڪس سڀ کان وڏو مستطيل سب ميٽرڪس ٺاهيندو آهي جنهن ۾ XNUMXs ۽ XNUMXs برابر آهن.

Dimesnions = 2 x 4
Matrix:
0 0 1
0 1 1
6

وضاحت: ڇو ته شروعاتي ميٽرڪس ۾ 0s ۽ 1s جو ساڳيو تعداد هو ، تنهن ڪري شروعاتي ميٽرڪس اسان جو جواب هوندو. اهو معاملو هتي آهي.

چرچو

نائي اچڻ وارو

اسان جو تمام آسان ڪم ، هر چوٽي تي ذيلي ميٽرڪس جي انڊيڪس جي هر چار طرفن لاءِ چار پوائنٽ تي غور ڪرڻ آهي. جڏهن اسان ذيلي ميٽرڪس درست ڪيو ته اسان 0s ۽ 1s جو انگ شمار ڪري سگهون ٿا. پر اهو ڪو ڪارائتو رويو ناهي ۽ وقت جي رڪاوٽن کان ضرور اڳتي ٿيندو. اسان مسئلي کي ٿورو گھٽائي سگھون ٿا جيڪڏهن اسان هر 0 کي -1 سان تبديل ڪريون. ان کان پوءِ ، اسان 2D اڳئين سيمي ٽيڪنڪي استعمال ڪندي ذيلي ميٽرڪس جو مجموعو ڳوليندا آهيون. پر جيتوڻيڪ اهو استعمال ڪرڻ ڪافي ناهي.

ايڏي موثر رستو

هڪ ڪارائتو رويو اهو ٿيندو ته پهريان هر 0 کي منفي ۾ تبديل ڪيو 1. بعد ۾ ، مسئلو سڀني نن subن ميٽڪس ڳولڻ جي لاءِ گھٽجي ويو 0. اسان هن مسئلي کي پهريان ئي coveredڪي چڪا آهيون. اهو مسئلو استعمال ڪندي حل ٿي ويو آهي متحرڪ پروگرامنگ. اسان کاٻي ۽ سا columnي ڪالمن کي درست ڪيو. پوء هر قطار جي عناصر جي رقم کي پهرين ڪالمن کان ٻئي ڪالمن تائين عارضي صف ۾ ذخيرو ڪيو. ان کان پوء اسان هڪ نقشو ٺاهيندا آهيون ، جتي اسين قطار جي نمبرن کي انگن جي مجموعي سان برابر ڪندا آهيون جڏهن ته عارضي طور تي هن سرورس کي پار ڪندي رهياسين. تنهن ڪري ، جيڪڏهن اسان ٻيهر ٻيهر ساڳيو عارضي قدر اسان جي عارضي ترتيب ۾ اچي. اسان کي پڪ آهي ته جيڪڏهن اسان قطار مان عناصر تي غور ڪيو ، في الحال نقشي ۾ محفوظ ڪيو پيو وڃي ته هاڻوڪي قطعي جي موجوده قيمت جي مقابلي ۾ ، اسان جو تعداد 0 هوندو. ۽ جڏهن اسان 0 کي -1 ۾ تبديل ڪيو ، اسان سڀني کي وڏي علائقي جي مستطيل ذيلي کان تبديل ڪيو هو. -ميڪس کي 1 جي برابر نمبر ۽ 0 جي تلاش کي مسئلو آهي سڀ کان وڏو ذيلي ميٽرڪ رقم 0 ۽ هاڻي اسان انهي سان گڏ آهيون.

ڪوڊ سڀني کان وڏو علائقو مستطيل ذيلي ميٽرڪس ڳولڻ جو 1 ۽ 0 جي برابر عدد سان

سي ++ ڪوڊ

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

int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (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 equal numbers of 0s and 1s"<<endl;
        return 0;
    }
    cout<<"Largest Sub-matrix with equal number of 1s and 0s"<<endl;
    for(int i=startRow;i<=endRow;i++){
        for(int j=startCol;j<=endCol;j++){
            cout<<(matrix[i][j]>0 ? 1 :  0)<<" ";
        }
        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];
                matrix[i][j] = matrix[i][j] ? 1 : -1;
            }
        }
        int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s(matrix, n, m);
        if(ans != 0)
        cout<<ans<<endl;
    }
}
1
4 4
1 1 1 1
0 1 0 1
1 0 1 0 
1 0 0 0
Largest Sub-matrix with equal number of 1s and 0s
1 1 1
1 0 1
0 1 0
0 0 0
12

جاوا ڪوڊ

import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
    static int largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (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 equal number of 1s and 0s");
            return 0;
        }
        System.out.println("Largest Rectangular Sub-matrix with equal number of 1s and 0s");
        for(int i=startRow;i<=endRow;i++){
            for(int j=startCol;j<=endCol;j++){
                System.out.print((matrix[i][j]>0) ? "1 " : "0 ");
            }
            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();
                    matrix[i][j] = matrix[i][j]>0 ? 1 : -1;
                }
            }
            int ans = largestAreaRectangularSubMatrixWithEqualNumberOf1sAnd0s (matrix, n, m);
            if(ans != 0)
            System.out.println(ans);
        }
    }
}
1
4 4
1 1 1 1
0 1 0 1
1 0 1 0
1 0 0 0
Largest Rectangular Sub-matrix with equal number of 1s and 0s
1 1 1
1 0 1
0 1 0
0 0 0
12

پيچيدگي تجزيي

وقت جي پيچيدگي: اي (اين ^ 3)

اسان وٽ O polinomial-time پيچيدگي وارو O (N ^ 3) ڇاڪاڻ ته اتي ٽي نالا آهن ٻيڙيون. اڳئين سم ۽ نقشي جي ٽيڪنڪ استعمال ڪندي صفر سم کي ڳولڻ لاءِ هڪ لوپ استعمال ٿيندو آهي.

خلائي پيچيدگي: اي (اين ^ 2)

جتان اسان هڪ 2D اڳوڻ سم آرڪ ٺاهيو. اهڙيء طرح ، وڏو علائقو مستطيل ذيلي ميٽرڪس 1 جي ۽ سڀني جي برابر عدد سان پولونوميل خلائي پيچيدگي آهي. اسان وٽ خلائي پيچيدگي آهي O (N ^ 0).