Maximum Size Square Sub Matrix With All 1s

Finding the largest square sub-matrix composed entirely of 1s in a given binary matrix is a common challenge in grid-based problems. In this article, you will learn how to efficiently solve this problem using dynamic programming.

Problem Statement

Given a 2D binary matrix (a matrix containing only 0s and 1s), the problem is to find the largest square sub-matrix that contains only 1s and return its area. This problem often arises in areas like image processing, where contiguous regions of a certain type need to be identified.

Example

Consider the following input binary matrix:

0 1 1 0 1
1 1 1 1 0
1 1 1 1 0
1 1 0 0 0

The output for this matrix would be 9, corresponding to a 3x3 square of 1s. The largest square starts at row 1, column 1 (0-indexed) and extends to row 3, column 3.

Background & Knowledge Prerequisites

To effectively understand the solution, a basic understanding of the following concepts is helpful:

• 2D Arrays: How to represent and access elements in a two-dimensional grid.
• Iteration: Looping through elements of a matrix.
• Dynamic Programming (DP): The concept of breaking down a problem into smaller overlapping subproblems and storing their solutions to avoid recomputation.

Use Cases or Case Studies

Identifying the largest square sub-matrix with all 1s has several practical applications:

• Image Processing: Detecting large, homogeneous regions in binary images, such as finding a large white block in a black and white image.
• Game Development: In grid-based games, it can be used for pathfinding, collision detection, or identifying areas suitable for building large structures.
• Resource Allocation: In a grid representing available resources, it can help locate the largest contiguous block of available resources for a specific task.
• Circuit Design: Identifying the largest square area of connected components in a circuit layout.
• Data Analysis: Finding patterns or clusters in binary data representations.

Solution Approaches

1. Brute Force Approach

The most straightforward, but inefficient, approach is to check every possible square sub-matrix in the given matrix.

• Summary: Iterate through all possible top-left corners (i, j) and for each, iterate through all possible square sizes k. For each potential square of size k, verify if all its cells contain '1'.
• Explanation:

1. Start by picking every cell (i, j) as the potential top-left corner of a square.
2. From (i, j), try to form squares of increasing size k = 1, 2, 3, ... up to the limits of the matrix.
3. For each square of size k, iterate through all its cells (row, col) where i <= row < i+k and j <= col < j+k. If any cell contains a 0, this square is invalid.
4. Keep track of the maximum k found that formed a valid square.
   • Complexity:

Time Complexity: O((MN)^2 * min(M,N)). This is highly inefficient for larger matrices, as it involves nested loops to pick top-left corners, square sizes, and then to check each cell within the square.

Space Complexity: O(1), as no extra space is used beyond input.

2. Dynamic Programming Approach

A more efficient way to solve this problem leverages dynamic programming by building a DP table.

• Approach Title: Dynamic Programming with Auxiliary Matrix
• One-line Summary: Create an auxiliary DP matrix where dp[i][j] stores the size of the largest square sub-matrix with all 1s ending at (i-1, j-1).
• Code Example:

// Maximum Size Square Sub-matrix with All 1s
#include <stdio.h>

// Function to find the maximum size square sub-matrix with all 1s
int maxSquare(int M[][5], int R, int C) {
    // dp[i][j] stores the size of the largest square sub-matrix with all 1s
    // ending at M[i-1][j-1]
    int dp[R + 1][C + 1];
    int max_square_size = 0; // Stores the maximum size found

    // Initialize first row and first column of dp table (conceptually)
    // For convenience, we use 1-indexed dp array, so dp[0][j] and dp[i][0] are 0.
    for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            dp[i][j] = 0;
        }
    }

    // Fill the dp table
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            // If the current cell in the original matrix is 1
            if (M[i - 1][j - 1] == 1) {
                // The size of the square ending at M[i-1][j-1] is 1 +
                // the minimum of the squares ending at its top, left, and top-left neighbors.
                int min_val = dp[i - 1][j]; // Top
                if (dp[i][j - 1] < min_val) { // Left
                    min_val = dp[i][j - 1];
                }
                if (dp[i - 1][j - 1] < min_val) { // Top-left
                    min_val = dp[i - 1][j - 1];
                }
                dp[i][j] = 1 + min_val;

                // Update the overall maximum square size
                if (dp[i][j] > max_square_size) {
                    max_square_size = dp[i][j];
                }
            } else {
                // If the current cell is 0, no square can end here, so dp[i][j] remains 0.
                dp[i][j] = 0;
            }
        }
    }

    return max_square_size * max_square_size; // Return the area
}

int main() {
    // Example 1
    int matrix1[4][5] = {
        {0, 1, 1, 0, 1},
        {1, 1, 1, 1, 0},
        {1, 1, 1, 1, 0},
        {1, 1, 0, 0, 0}
    };
    int R1 = 4;
    int C1 = 5;
    printf("Matrix 1:\\n");
    for (int i = 0; i < R1; i++) {
        for (int j = 0; j < C1; j++) {
            printf("%d ", matrix1[i][j]);
        }
        printf("\\n");
    }
    printf("Max square area for Matrix 1: %d\\n\\n", maxSquare(matrix1, R1, C1));

    // Example 2
    int matrix2[3][3] = {
        {1, 0, 1},
        {1, 1, 1},
        {0, 1, 1}
    };
    int R2 = 3;
    int C2 = 3;
    printf("Matrix 2:\\n");
    for (int i = 0; i < R2; i++) {
        for (int j = 0; j < C2; j++) {
            printf("%d ", matrix2[i][j]);
        }
        printf("\\n");
    }
    printf("Max square area for Matrix 2: %d\\n\\n", maxSquare(matrix2, R2, C2));

    return 0;
}

Run

• Sample Output:

Matrix 1:
0 1 1 0 1
1 1 1 1 0
1 1 1 1 0
1 1 0 0 0
Max square area for Matrix 1: 9

Matrix 2:
1 0 1
1 1 1
0 1 1
Max square area for Matrix 2: 4

• Stepwise Explanation:

1. Create DP Table: Initialize an auxiliary DP table dp of size (R+1) x (C+1) with all zeros. dp[i][j] will store the size of the largest square sub-matrix with all 1s ending at matrix[i-1][j-1]. We use 1-indexed dp for easier boundary handling with the matrix's 0-indexing.
2. Iterate and Fill: Traverse the original matrix M from (0,0) to (R-1, C-1). For each cell M[i-1][j-1] (corresponding to dp[i][j]):
   • If M[i-1][j-1] is 1: The current cell can potentially extend a square. The size of the square ending at (i-1, j-1) will be 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

dp[i-1][j] represents the largest square ending at the cell directly above M[i-1][j-1].

dp[i][j-1] represents the largest square ending at the cell directly to the left of M[i-1][j-1].

dp[i-1][j-1] represents the largest square ending at the cell diagonally top-left of M[i-1][j-1].

Taking the minimum ensures that the new square formed with M[i-1][j-1] as its bottom-right corner is entirely composed of 1s.

• If M[i-1][j-1] is 0: A square of 1s cannot end at this cell, so dp[i][j] is 0.

1. Track Maximum: During the iteration, keep track of the maximum value encountered in the dp table. This max_square_size will be the side length of the largest square.
2. Calculate Area: The final result is max_square_size * max_square_size.
   • Time Complexity: O(R*C), as each cell in the dp table is visited and processed once.

Space Complexity: O(R*C) for the dp auxiliary matrix. This can be optimized to O(C) by only keeping track of the previous row's DP values.

Conclusion

Finding the maximum size square sub-matrix with all 1s is a classic dynamic programming problem. While a brute-force approach exists, it is inefficient for larger inputs. The dynamic programming approach significantly optimizes the solution by building an auxiliary table, allowing for the reuse of computed results and reducing the time complexity to linear with respect to the matrix dimensions.

Summary

• The problem involves finding the largest square sub-matrix containing only 1s within a binary matrix.
• A naive brute-force approach checks every possible square, leading to high time complexity.
• The dynamic programming solution uses an auxiliary dp table.
• dp[i][j] stores the side length of the largest square of 1s ending at (i-1, j-1).
• The recurrence relation is dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if matrix[i-1][j-1] is 1, otherwise it's 0.
• The maximum value in the dp table represents the side length of the largest square.
• The time complexity is O(R*C) and space complexity is O(R*C), which can be optimized to O(C).