在填充有1的矩阵中找到最大尺寸的正方形

1. Overview

In this tutorial, we’ll discuss finding the maximum square size filled with ones in a matrix that contains only zeros and ones.

Firstly, we’ll define the problem. Then we’ll give an example to explain it.

After that, we’ll present four different approaches to solving this problem.

2. Defining the Problem

We’re given a binary matrix of size $N \times M$ (containing rows and columns). Each cell of the matrix has a value equal to either zero or one. We’re asked to find the maximum side length of a sub-matrix that’s full of ones.

Let’s take a look at the following example for a better understanding:

FullOnes 1

we’ll represent the sub-matrix as two tuples (x_1, y_1) and (x_2, y_2) , which represent the position of the top-left corner and the bottom-right corner respectively.

As we can see, the sub-matrix (2, 2) and (4, 4) is the biggest square sub-matrix which is full of ones. It has a size equal to $3 \times 3$ , so the answer for the given example is , which represents the length of the square’s side.

3. Brute Force Approach

3.1. Main Idea

The idea in this approach is to loop over all the cells of the given matrix. For each cell, we fix it as the top-left corner and check every possible square length.

For each length, we get the bottom-right corner by adding the length - 1 to the coordinates of the top-left corner (i, j) , which represents the current fixed cell. To check whether the current square is full of ones, we’ll iterate over all the cells of this sub-matrix and check if they’re equal to one.

In the end, if the current square is valid, we’ll maximize our answer with the current length to get the length of the maximum square full of ones.

3.2. Checking a Full Square

First, let’s implement the function that will check whether a given square matrix is filled with ones:

algorithm CheckIfSquareIsFullOfOnes(TL, BR):
    // INPUT
    //    TL = the top-left corner of the square (TL.x, TL.y)
    //    BR = the bottom-right corner of the square (BR.x, BR.y)
    // OUTPUT
    //    true if the square is full of ones, false otherwise

    for i <- TL.x to BR.x:
        for j <- TL.y to BR.y:
            if G[i, j] = 0:
                return false

    return true

We iterate over each cell in the sub-matrix. If the value of the current cell is equal to zero, then we return false .

Otherwise, if we reach the end and don’t find any zeros, that means the sub-matrix is full of ones. As a result, we return true .

3.3. Algorithm

Let’s take a look at the implementation of the algorithm:

algorithm BruteForceApproach(N, M):
    // INPUT
    //    N = the number of rows in the matrix
    //    M = the number of columns in the matrix
    // OUTPUT
    //    The length of the maximum square sub-matrix that is full of ones

    answer <- 0

    for i <- 1 to N:
        for j <- 1 to M:
            for len <- 1 to Min(N, M):
                if i + len > N or j + len > M:
                    break
                if isFull((i, j), (i + len - 1, j + len - 1)):
                    answer <- Max(answer, len)

    return answer

Initially, we declare answer , which will store the answer for our problem. Then, we iterate over each cell of the given matrix and fix it as the top-left corner of the square sub-matrix.

Next, we try to check every possible length. If the current length generates a square that doesn’t fit in the matrix, we break out of the loop.

Otherwise, we check if the square sub-matrix that has top-left corner (i, j) and bottom-right corner (i + len - 1, j + len - 1) is full of ones. If so, that means there’s a square with a side length equal to len . So, we maximize the answer to equal the maximum value between the previous answer and the current length.

Finally, the answer will have the length of the maximum square that’s full of ones.

3.4. Complexity

The complexity of this algorithm is $\boldsymbol{O(N^{2} \times M^{2} \times L)}$ , where is the number of rows, is the number of columns, and is the maximum possible length of a square side which is in the worst-case equal to Min(N, M) .

The reason behind this complexity is that we’ll iterate over each cell once with complexity equal to O(N.M) . On the other hand, for each cell, we try every possible length with complexity that is equal to O(L) .

In addition, for every length, we check if the square is full of ones or not, which has a complexity equal to O(N.M) .

That leaves us with total complexity equal to $O(N^{2} \times M^{2} \times L)$ .

4. Dynamic Programming Optimization

4.1. Main Idea

In this approach, we’ll use the same idea as the previous approach. However, we’ll optimize the isFull function and make it run in O(1) complexity instead of $O(N \times M)$ .

We’ll use the 2D prefix sum technique, a dynamic programming optimization, to get the sum of sub-matrix in constant time complexity. The main idea in this technique is to create a $\boldsymbol{prefix}$ matrix which, inside $\boldsymbol{prefix[i][j]}$ , stores the sum of all the elements in the sub-matrix (1, 1), (i, j).

The formula to build this matrix is:

$[\boldsymbol{Prefix[i][j] = Matrix[i][j] + Prefix[i][j - 1] + Prefix[i - 1][j] - Prefix[i - 1][j - 1]}]$

The sum of the sub-matrix (1, 1), (i, j) can be obtained by taking the sum of sub-matrices (1, 1), (i, j – 1) and (1, 1), (i – 1, j). However, in this case, we have added the sum of (1, 1), (i – 1, j – 1) twice. Thus, we delete it from the answer. Also, we didn’t include the current cell (i, j), so we add it to the prefix value.

If we want to get the sum of a specific sub-matrix (x_1, y_1) , (x_2, y_2) , we’ll get the sum at the bottom-right corner prefix[x_2][y_2] .

Then, we’ll subtract prefix[x_2][y_1 - 1] which corresponds to the sum of the sub-matrix (1, 1) , (x_2, y_1 - 1) . Also, we’ll subtract prefix[x_1 - 1][y_2] which represents the sum of the sub-matrix (1, 1) , (x_1 - 1, y_2) .

Finally, we add prefix[x_1 - 1][y_1 - 1] which is the sum of the sub-matrix (1, 1) , (x_1 - 1, y_1 - 1) because we deleted this sub-matrix twice when we removed the previous two sub-matrices.

Let’s take the following example:

FullOnes 2

The sum of the sub-matrix (2, 2), (4, 4) can be calculated by taking the following 2D prefix values:

[sum = prefix[4][4] - prefix[4][1] - prefix[1][4] + prefix[1][1]]

4.2. Algorithm

Let’s take a look at the enhanced implementation of the isFull function:

algorithm CheckIfSquareIsFullOfOnes(TL, BR):
    // INPUT
    //    TL = the top-left corner of the square (TL.x, TL.y)
    //    BR = the bottom-right corner of the square (BR.x, BR.y)
    // OUTPUT
    //    true if the square is full of ones, false otherwise

    area <- (BR.x - TL.x + 1) * (BR.y - TL.y + 1)
    sum <- prefix[BR.x, BR.y]
    sum <- sum - prefix[BR.x, TL.y - 1]
    sum <- sum - prefix[TL.x - 1, BR.y]
    sum <- sum + prefix[TL.x - 1, TL.y - 1]

    if sum = area:
        return true
    else:
        return false

The isFull function will take the top-left and the bottom-right corners as parameters. Next, we’ll calculate the area of the sub-matrix, which represents the number of cells in the sub-matrix.

After that, we’ll use the 2D prefix sum technique to get the sum of the elements in the sub-matrix, which represents the number of ones in the sub-matrix.

Finally, if the value of sum is equal to the value of area (number of ones equal to the number of cells), that means the given sub-matrix is full of ones. Otherwise, it’s not.

4.3. Complexity

The complexity of this algorithm is $\boldsymbol{O(N \times M \times L)}$ , where is the number of rows, is the number of columns, and is the maximum possible length of a square side which is in the worst-case equal to Min(N, M) .

The reason behind this complexity is the same as the previous approach, but instead of checking if a sub-matrix is full of one in O(N.M) complexity, we did it in constant time O(1) .

In addition, before starting our algorithm, we’ll calculate the values of array, but this will have a complexity equal to $\boldsymbol{O(N \times M)}$ , which is less than the complexity of the algorithm itself.

5. Binary Search Approach

5.1. Main Idea

In this approach, we’ll use the binary search algorithm to find the maximum valid length in $\boldsymbol{O(Log_2(L))}$ .

The reason why binary search works here is that, while we iterate over the top-left corner, if there’s a square full of ones of size , that means all the squares of sizes [1, 2, 3, ..., L] are also filled with ones. The reason is that the square of size is a sub-matrix of the square of size L + 1 .

On the other hand, if there’s a square that isn’t filled with ones of size , that means all the squares of size [L, L + 1, ....] are also not filled with ones.

5.2. Algorithm

Let’s take a look at the implementation:

algorithm BinarySearchApproach(N, M):
    // INPUT
    //    N = the number of rows in the matrix
    //    M = the number of columns in the matrix
    // OUTPUT
    //    The length of the maximum square that is full of ones

    answer <- 0

    for i <- 1 to N:
        for j <- 1 to M:
            low <- 1
            high <- Min(N - i, M - j)

            while low <= high:
                len <- (low + high) / 2

                if isFull((i, j), (i + len - 1, j + len - 1)):
                    answer <- Max(answer, len)
                    low <- len + 1
                else:
                    high <- len - 1

    return answer

Initially, we declare answer , which will store the answer for our problem. Then, we iterate over each cell of the given matrix and fix it as the top-left corner of the square sub-matrix.

Next, we’ll find the maximum valid length using binary search. During the binary search algorithm, if the current length is valid (gives us a square full of ones), then we’ll try to maximize the answer and look for a bigger length. Otherwise, the current length is not valid, and we’ll try to find a smaller length that gives us a square full of ones.

Finally, the answer will have the length of the maximum square that’s full of ones.

5.3. Complexity

The complexity of this algorithm is $\boldsymbol{O(N \times M \times Log_2(L))}$ , where is the number of rows, is the number of columns, and is the maximum possible length of a square side which is in the worst-case equal to Min(N, M) .

The reason behind this complexity is the same as the previous approach, where we enhanced the isFull function. Still, instead of looping over all the possible lengths, we found the perfect length using binary search technique in complexity O(Log_2(L)) , instead of O(L) .

6. Two Pointers Approach

6.1. Main Idea

The main idea here is that there’s no need to repeat the search for a perfect length over and over again for each cell.

Instead, when we find a valid length $\boldsymbol{L}$ , we don’t have to check lengths $\boldsymbol{[1, 2, 3, .., L]}$ again since we already have a square full of ones of length $\boldsymbol{L}$ . Now, we’ll just be looking for a bigger square full of ones.

6.2. Algorithm

Let’s take a look at the implementation:

algorithm BinarySearchApproach(N, M):
    // INPUT
    //    N = the number of rows in the matrix
    //    M = the number of columns in the matrix
    // OUTPUT
    //    len = the maximum side length of a sub-matrix full of ones

    len <- 0

    for i <- 1 to N:
        for j <- 1 to M:
            while (i + len <= N) and (j + len <= M)
              and isFull((i, j), (i + len, j + len)):
                len <- len + 1

    return len

Initially, we declare len , which will represent the maximum length we have at this moment. Also, it’ll be the answer to our problem.

Then, we iterate over each cell of the given matrix and fix it as the top-left corner of the square sub-matrix. Next, as long as we have a square full of ones of the current length, and we didn’t exceed the boundaries of the matrix, we increase the len to find a bigger square.

Finally, the len value will have the length of the maximum square that’s full of ones.

6.3. Complexity

The complexity of this algorithm is $\boldsymbol{O(N \times M + L)}$ , where is the number of rows, is the number of columns, and is the maximum possible length of a square side which is in the worst-case equal to Min(N, M) .

The reason behind this complexity is that we iterate over each cell once in the complexity of $O(N \times M)$ .

In addition, we don’t reduce the value of len . Instead, to find the perfect length, we iterate over each length at most once since when we find a valid length , we don’t recheck all the previous lengths.

7. Conclusion

In this article, we presented the problem of finding the maximum square that’s full of ones.

First, we provided an example to explain the problem. Then, we gave four different approaches to solving it.

Finally, we walked through their implementations, with each approach having a better time complexity than the previous one.

Persistence

REST

Security