1과 0의 수가 동일한 가장 큰 영역의 직사각형 부분 행렬


난이도 하드
자주 묻는 질문 Accenture 과연 정보 가장자리 모노 타입 솔루션 페이팔 클립 Synopsys 타임즈 인터넷 UHG 옵텀
배열 동적 프로그래밍 매트릭스

문제 정책

nx m 크기의 이진 행렬이 주어집니다. 문제는 동일한 수의 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로 변경하면 문제를 약간 최적화 할 수 있습니다. 그 후 XNUMXD 접두사 합법을 사용하여 부분 행렬의 합을 찾습니다. 그러나 그것을 사용하는 것만으로는 충분하지 않습니다.

효율적인 접근

효율적인 접근 방식은 먼저 행렬의 각 0을 음수 1로 변경하는 것입니다. 그 후 문제는 합계가 0 인 가장 큰 부분 행렬을 찾는 것으로 줄어 듭니다. 우리는 이미이 문제를 다뤘습니다. 이 문제는 동적 프로그래밍. 왼쪽 및 오른쪽 열을 수정합니다. 그런 다음 첫 번째 열에서 두 번째 열까지 각 행의 요소 합계를 임시 배열에 저장합니다. 그런 다음이 임시 배열을 순회하면서 요소의 합에 해당하는 행 번호를 저장하는 맵을 만듭니다. 따라서 임시 배열에서 동일한 합계 값을 다시 만나면. 현재 행의 합계 값과 비교하여 현재 맵에 저장되어있는 행의 요소는 합계가 0이 될 것이라고 확신합니다. 0을 -1로 변경했을 때 가장 큰 사각형 하위 영역에서 변환 한 것입니다. -같은 수의 1과 0의 문제를 가진 행렬 합계가 0 인 가장 큰 부분 행렬 이제 끝났습니다.

1과 0의 수가 동일한 가장 큰 영역의 직사각형 부분 행렬을 찾는 코드

C ++ 코드

#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

복잡성 분석

시간 복잡성: O (N ^ 3)

다항식 시간 복잡도는 O (N ^ 3)입니다. 루프. 하나의 루프는 접두사 Sum 및 맵 기술을 사용하여 제로 합계를 찾는 데 사용됩니다.

공간 복잡성: O (N ^ 2)

2D 접두사 Sum 배열을 만들었 기 때문에. 따라서 1과 0의 수가 동일한 문제가있는 최대 면적 직사각형 부분 행렬은 다항식 공간 복잡도를 갖습니다. 우리는 O (N ^ 2)의 공간 복잡도를 가지고 있습니다.