Finding largest square submatrix of ones in a given square matrix of 0's and 1's?

Question

The following was given as an interview question:

Write a function that outputs the size of the largest square submatrix consisting solely of ones in a square matrix of ones and zeros.

Example 1:

0 1
0 0

Output: 1

Example 2:

0 0 0
0 1 1
0 1 1

Output: 2

Example 3:

1 1 1
1 1 1
1 1 1

Output 3

I was hoping for an efficient solution to this problem if at all possible.

What work have you done so far? We aren't going to just answer this for you. — chrisaycock, Dec 09 '10 at 05:17
I'm pretty sure this exact question has been asked here on Stack Overflow before, maybe a year ago or two. — ShreevatsaR, Dec 09 '10 at 06:39
possible duplicate of [Dynamic programming - Largest square block](http://stackoverflow.com/questions/1726632/dynamic-programming-largest-square-block) — ShreevatsaR, Dec 09 '10 at 06:40
Possible duplicate of [Finding maximum size sub-matrix of all 1's in a matrix having 1's and 0's](http://stackoverflow.com/questions/3806520/finding-maximum-size-sub-matrix-of-all-1s-in-a-matrix-having-1s-and-0s) — aerin, Apr 12 '17 at 20:19

score 2 · Answer 1 · edited May 23 '17 at 12:25

2

Use Search and then Dynamic Programming.

edited May 23 '17 at 12:25

Community

1
1

answered Dec 09 '10 at 06:10

Chris Hopman

2,082
12
11

score 0 · Answer 2 · answered Apr 12 '17 at 20:18

Here is O(n) implementation in C# using dynamic programming. Basically you are building another matrix of biggest size (including itself) while you are reading every cell of the matrix.

    public static int LargestSquareMatrixOfOne(int[,] original_mat)
    {
        int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)];
        AccumulatedMatrix[0, 0] = original_mat[0, 0];
        int biggestSize = 1;
        for (int i = 0; i < original_mat.GetLength(0); i++)
        {
            for (int j = 0; j < original_mat.GetLength(1); j++)
            {
                if (i > 0 && j > 0)
                {
                    if (original_mat[i, j] == 1)
                    {
                        AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1;
                        if (AccumulatedMatrix[i, j] > biggestSize)
                        {
                            biggestSize = AccumulatedMatrix[i, j];
                        }
                    }
                    else
                    {
                        AccumulatedMatrix[i, j] = 0;
                    }
                }
                else if ( (i > 0 && j == 0) || (j > 0 && i == 0))
                {
                    if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; }
                    else { AccumulatedMatrix[i, j] = 0; }
                }
            }
        }
        return biggestSize;
    }

score 0 · Answer 3 · answered Feb 12 '11 at 08:40

First idea of implementation: Start search on row r=1.

Find longest sequence of ones in that row, and assign this length to x.

Try to find a square matrix of ones with side=x starting at row r. If successful, max=x. If not, decrease x and repeat this step if x>1. If nothing found, max could be 0 or 1.

Increase r, and repeat.

Then improve your algorithm (stop if remaining rows are less than current max, and so on).

Finding largest square submatrix of ones in a given square matrix of 0's and 1's?

3 Answers3