1 आणि 0 च्या समान संख्येसह सर्वात मोठे क्षेत्र आयताकृती उप-मॅट्रिक्स


अडचण पातळी हार्ड
वारंवार विचारले ऐक्सचर खरंच माहिती काठ मोनोटाइप सोल्यूशन्स पोपल करा सारांश टाइम्स इंटरनेट यूएचजी ऑप्टम
अरे डायनॅमिक प्रोग्रामिंग मॅट्रिक्स

समस्या विधान

एनएक्स मीटर आकाराचे बायनरी मॅट्रिक्स दिले. 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 एस समान संख्येसह सर्वात मोठे आयताकृती उप-मॅटिक्स बनवते.

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

स्पष्टीकरणः प्रारंभिक मॅट्रिक्सची 0 आणि 1 एस समान संख्या असल्याने प्रारंभिक मॅट्रिक्स आमचे उत्तर असेल. अशीच परिस्थिती येथे आहे.

दृष्टीकोन

भोळे दृष्टिकोन

आम्ही करू शकणारी सर्वात सोपी गोष्ट म्हणजे चारही दिशांना सब-मॅट्रिक्सच्या निर्देशांकांकरिता प्रत्येकी चार-पॉईंटर्सचा विचार करणे. जेव्हा आम्ही सब-मॅट्रिक्स निश्चित करतो तेव्हा 0 आणि 1 एसची संख्या मोजू शकतो. परंतु हा कार्यक्षम दृष्टीकोन नाही आणि वेळ मर्यादा निश्चितच ओलांडेल. आम्ही प्रत्येक 0--1 सह बदलल्यास आम्ही समस्या थोडी अनुकूल करू शकतो. त्यानंतर, आम्हाला 2 डी उपसर्ग सम तंत्रात उप-मॅट्रिक्सची बेरीज मिळते. परंतु तरीही ते वापरणे पुरेसे होणार नाही.

कार्यक्षम दृष्टीकोन

प्रथम मॅट्रिक्समध्ये नकारात्मक १ सह प्रत्येक ० बदलणे ही एक कार्यक्षम पध्दत असेल. त्यानंतर, ही समस्या कमी होणारी सर्वात मोठी सब-मॅट्रिक्स शोधण्यासाठी कमी होईल. आम्ही आधीपासूनच ही समस्या व्यापून टाकली आहे. याचा उपयोग करून ही समस्या सुटली आहे डायनॅमिक प्रोग्रामिंग. आम्ही डावे आणि उजवे स्तंभ निराकरण करतो. नंतर प्रथम पंक्तीपासून दुसर्‍या स्तंभात प्रत्येक पंक्तीच्या घटकांची बेरीज तात्पुरती अ‍ॅरेमध्ये संचित करा. नंतर आम्ही एक नकाशा बनवितो, जिथे आम्ही या तात्पुरत्या अ‍ॅरेचा आढावा घेत घटकांच्या बेरीजशी संबंधित पंक्ती क्रमांक संग्रहित करतो. जर आपल्याला पुन्हा तात्पुरते अ‍ॅरेमध्ये समान बेरीज मूल्य आढळली तर. आम्हाला खात्री आहे की जर आपण सध्याच्या ओळीच्या बेरीज मूल्याच्या विरूद्ध नकाशामध्ये सध्याच्या ओळीतील घटकांचा विचार केला तर त्याची संख्या 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)

आमच्यात ओ (एन ^ 3) ची बहुपदीय जटिलता आहे कारण तेथे तीन नेस्टेड आहेत लूप. प्रत्येकी योग आणि नकाशा तंत्राचा वापर करून शून्य बेरीज शोधण्यासाठी एक लूप वापरला जातो.

स्पेस कॉम्प्लेक्सिटी: ओ (एन ^ 2)

आम्ही 2D उपसर्ग Sum अ‍ॅरे केल्यापासून. अशा प्रकारे 1 आणि 0 च्या समान संख्येसह सर्वात मोठे क्षेत्र आयताकृती उप-मॅट्रिक्समध्ये बहुपदी जागेची गुंतागुंत असते. आमच्याकडे ओची अवघडपणा (एन. 2) आहे.