Find the largest sub-matrix full of units in linear time

Question

Given a matrix n by n with zeros and ones, find the largest sub-matrix full of units in linear time. I was told that the solution with O (n) is of temporary complexity. If there are n ^ 2 elements in an n X n matrix, how does a linear solution exist?

Answer 1

You cannot find the matrix n x nin ntime. Counterexample: matrix of zeros with one element set to unity. You must check each item to find where it is, so the time should be at least O(n^2).

Now, if you say that there are n= entries in the matrix n^2, and you only look at the submatrices that form a continuous block, then you should be able to find the largest submatrix by walking diagonally along the matrix, tracking each rectangle as you go. In the general case, you could have up O(sqrt(N))rectangles at the same time, and you would need to look in them to find out which rectangle was the largest, so you should be able to do this in O(N^(3/2) * log(N))time.

If you can select arbitrary rows and columns to form your submatrix, then I do not see any obvious polynomial time algorithm.

Answer 2

, NP- .

Answer 3

The solution is linear in the number of records, not in the number of rows or columns.

Answer 4

public static int biggestSubMatrix(int[][] matrix) {

    int[][] newMatrix = new int[matrix.length][matrix[0].length];

    for (int i = 0; i < matrix.length; i++) {
        int sum = 0;
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 1) {
                sum++;
                newMatrix[i][j] = sum;
            } else {
                sum = 0;
                newMatrix[i][j] = 0;
            }
        }
    }


    int maxDimention = 0;
    int maxSubMatrix = 0;

    for (int i = 0; i < newMatrix[0].length; i++) {
        //find dimention for each column
        maxDimention = calcHighestDimentionBySmallestItem(newMatrix, i);
       if(maxSubMatrix < maxDimention ){
          maxSubMatrix  = maxDimention ;
         }
     }
    return maxSubMatrix;


}

private static int calcHighestDimentionBySmallestItem(int[][] matrix, int col) {

    int totalMaxDimention =0;

    for (int j = 0; j < matrix.length; j++) {
        int maxDimention = matrix[j][col];
        int numItems = 0;
        int min = matrix[j][col];
        int dimention = 0;

        for (int i = j; i < matrix.length; i++) {
            int val = matrix[i][col];
            if (val != 0) {
                if (val < min) {
                    min = val;
                }
                numItems++;
                dimention = numItems*min;
                if(dimention>maxDimention){
                    maxDimention = dimention;
                }

            } else {  //case val == 0
                numItems = 0;
                min = 0;

            }
        }
        if(totalMaxDimention < maxDimention){
            totalMaxDimention = maxDimention;
        }

    }
    return totalMaxDimention;
}