3

Given an n by n matrix with zeros and ones, find the largest sub- matrix full 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?

algo-geeks
  • 5,280
  • 10
  • 42
  • 54

4 Answers4

4

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

Rafał Dowgird
  • 43,216
  • 11
  • 77
  • 90
  • Assuming "submatrix" means "a matrix formed by a subset of rows and columns" -- right? – j_random_hacker Dec 20 '10 at 02:41
  • @j_random_hacker: Right. *Any* subsets, in particular non-contiguous ones - that's the standard definition. If you limit the choice to contiguous subsets then it is of course polynomial. – Rafał Dowgird Dec 20 '10 at 09:13
1

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.

Rex Kerr
  • 166,841
  • 26
  • 322
  • 407
  • You're about the fact a "linear" solution here would actually be O(n^2). However, I don't understand your solution. You can't just walk diagonally, e.g. some large submatrix could be located at the top right of the matrix. – ripper234 Feb 15 '11 at 06:38
  • @ripper234 - I wasn't clear enough. You propagate a line that looks like `/` from the top left to the lower right. If there is a large block at toe top right, the first part of it to be hit by the traveling line will be the single element at its top left corner, and it will then be swept out from top left to bottom right. – Rex Kerr Feb 15 '11 at 12:21
  • I have a question @Rex Kerr, you wrote that He can't search `nXn` matrix in `n` time, but if he will not check every element, insted, he will check the sum of each row and each column. can't this option leads to a solution with O(n) times ? (I'm asking because I really don't know) :) – Gil Peretz Feb 06 '13 at 10:05
  • @GilPeretz - It takes O(n^2) time to compute the sums of the rows and columns. Even if you had the sums and columns given to you for free, you'd still have to make additional assumptions about the structure in order to get a O(n) algorithm out (e.g. that it's block diagonal). – Rex Kerr Feb 06 '13 at 10:11
  • Thank you for your wisely answer @Rex – Gil Peretz Feb 06 '13 at 11:14
0

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

Oswald
  • 31,254
  • 3
  • 43
  • 68
  • 1
    agreed. But to confirm found set to be a matrix, don't we need O(n^2)? I hope the matrix with 1s is supposed to be n x n (and not just row or column matrix)... – mihsathe Dec 19 '10 at 10:20
0
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;
}
reem
  • 1
  • 1