find the largest sub- matrix full of ones in linear time

Given an n by n matrix with zeros and ones, find the largest sub- matrix ful开发者_开发知识库l of ones in linear time. I was told that a solution with O(n) time complexity exists. If there are n^2 elements in a n X n matrix how does a linear solution exist?

Unless you have a non-standard definition of submatrix this problem is NP-hard by reduction from maximum clique.

You can't search a n x n matrix in n time. Counterexample: a matrix of zeros with a single element set to one. You have to check every element to find where that one is, so time must be at least O(n^2).

Now if you say that the matrix has N = n^2 entries, and you only consider submatrices that form a contiguous block, then you should be able to find the largest submatrix by walking diagonally across the matrix, keeping track of every rectangle of ones as you go. You could in general have up to O(sqrt(N)) rectangles active simultaneously, and you would need to search in them to figure out which rectangle was the largest, so you ought to be able to do this in O(N^(3/2) * log(N)) time.

If you can pick arbitrary rows and columns to form your submatrix, then I don't see any obvious polynomial time algorithm.

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

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;
}