Maximum Size Of Square Submatrix With All 1s In A Binary Matrix in C++

Finding the maximum size of a square submatrix containing only 1s in a given binary matrix is a classic problem with applications in various fields. In this article, you will learn how to efficiently solve this problem using dynamic programming in C++.

Problem Statement

Given a 2D binary matrix matrix (composed of 0s and 1s), the objective is to find the largest square submatrix that contains only 1s and return its area. This problem often arises in image processing, game development (e.g., pathfinding, terrain analysis), and other grid-based optimization scenarios where identifying continuous regions is crucial.

Example

Consider the following binary matrix:

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

 

The largest square submatrix containing all 1s has a side length of 3, located at the center:

1 1 1
  1 1 1
  1 1 1

 

Thus, its area would be 3 * 3 = 9.

Background & Knowledge Prerequisites

To understand the solution presented, readers should have a basic understanding of:

• C++ Fundamentals: Variables, loops, conditional statements, functions, and standard data structures like vector.
• Dynamic Programming (DP): The concept of breaking down a problem into overlapping subproblems and storing the results to avoid redundant calculations.

 

Relevant C++ imports:

• iostream for input/output operations.
• vector for using dynamic arrays (2D matrices).
• algorithm for functions like min and max.

 

Use Cases or Case Studies

Here are a few practical applications for identifying the largest square submatrix of 1s:

• Image Processing: Identifying the largest square region of a specific feature (e.g., a solid color block) in a binary image.
• Game Development: Determining the largest clear square area for building placement, character movement, or explosive effects on a grid-based map.
• Resource Allocation: Finding the largest contiguous square area in a grid representing available resources, such as land plots or server space.
• Circuit Design: Identifying the largest square region of connected components in a circuit layout.
• Biological Data Analysis: Locating the largest square cluster of active cells or genes in a biological dataset represented as a grid.

 

Solution Approaches

While a brute-force approach (checking every possible square submatrix) is conceptually simple, it would be highly inefficient with a time complexity of O((rows * cols)^3). A much more efficient solution involves dynamic programming.

Dynamic Programming Approach

This approach leverages the results of smaller subproblems to build up the solution for the larger problem.

One-line summary: We create a DP table where each cell dp[i][j] stores the side length of the largest square submatrix ending at (i, j) that consists entirely of 1s.

Code example:

// Maximum Size Square Submatrix
#include <iostream>
#include <vector>
#include <algorithm> // For std::min and std::max

using namespace std;

int maximalSquare(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) {
        return 0;
    }

    int rows = matrix.size();
    int cols = matrix[0].size();
    
    // dp[i][j] stores the side length of the largest square submatrix
    // with all 1s ending at (i-1, j-1) in the original matrix.
    // We use (rows + 1) and (cols + 1) for easier boundary handling.
    vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, 0));
    int max_side = 0;

    // Iterate through the original matrix
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (matrix[i][j] == 1) {
                // If the current cell is '1', the size of the square ending here
                // depends on its top, left, and top-left neighbors in the DP table.
                dp[i + 1][j + 1] = 1 + min({dp[i][j + 1], dp[i + 1][j], dp[i][j]});
                
                // Update the maximum side found so far
                max_side = max(max_side, dp[i + 1][j + 1]);
            }
            // If matrix[i][j] is '0', then dp[i+1][j+1] remains 0 (default initialized)
            // as no square with all 1s can end at this position.
        }
    }

    return max_side * max_side; // Return the area
}

int main() {
    // Example 1: Matrix from the problem statement
    vector<vector<int>> matrix1 = {
        {1, 0, 1, 0, 0},
        {1, 0, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0}
    };
    cout << "Matrix 1: Max square area = " << maximalSquare(matrix1) << endl; // Expected: 9

    // Example 2: All 1s matrix
    vector<vector<int>> matrix2 = {
        {1, 1, 1},
        {1, 1, 1},
        {1, 1, 1}
    };
    cout << "Matrix 2: Max square area = " << maximalSquare(matrix2) << endl; // Expected: 9

    // Example 3: Single 1
    vector<vector<int>> matrix3 = {{1}};
    cout << "Matrix 3: Max square area = " << maximalSquare(matrix3) << endl; // Expected: 1

    // Example 4: No 1s
    vector<vector<int>> matrix4 = {
        {0, 0, 0},
        {0, 0, 0}
    };
    cout << "Matrix 4: Max square area = " << maximalSquare(matrix4) << endl; // Expected: 0

    return 0;
}

Run

Sample output:

Matrix 1: Max square area = 9
Matrix 2: Max square area = 9
Matrix 3: Max square area = 1
Matrix 4: Max square area = 0

 

Stepwise explanation:

1. Initialization:
   • Handle edge cases where the input matrix is empty.

• Create a dp table of size (rows + 1) x (cols + 1) and initialize all its values to 0. The extra row and column simplify boundary conditions, avoiding explicit checks for i=0 or j=0.
• Initialize max_side = 0 to keep track of the largest square side length found.

1. DP Table Population:
   • Iterate through the original matrix from (0, 0) to (rows-1, cols-1).

• For each cell matrix[i][j]:
• If matrix[i][j] is 1:
• The value dp[i+1][j+1] (corresponding to matrix[i][j]) is calculated as 1 + min(dp[i][j+1], dp[i+1][j], dp[i][j]).
• dp[i][j+1] represents the square size ending directly above the current cell.
• dp[i+1][j] represents the square size ending directly to the left of the current cell.
• dp[i][j] represents the square size ending diagonally top-left to the current cell.
• Taking the minimum of these three ensures that a square of that side length can indeed be formed with matrix[i][j] as its bottom-right corner. We add 1 because matrix[i][j] itself is a 1.
• Update max_side = max(max_side, dp[i+1][j+1]) to track the largest side length encountered.
• If matrix[i][j] is 0:
• dp[i+1][j+1] remains 0, as no square of 1s can end at a 0.

1. Result Calculation:
   • After iterating through the entire matrix, max_side will hold the maximum side length of any square submatrix with all 1s.

• Return max_side * max_side to get the area.

 

This dynamic programming approach processes each cell once, leading to a time complexity of O(rows \* cols) and a space complexity of O(rows \* cols) for the DP table.

Conclusion

The problem of finding the maximum size square submatrix with all 1s in a binary matrix is efficiently solved using dynamic programming. By carefully defining the DP state and recurrence relation, we can compute the solution in linear time with respect to the matrix dimensions, significantly outperforming brute-force methods.

Summary

• Problem: Find the largest square submatrix of all 1s in a binary matrix.
• Key Concept: Dynamic Programming.
• DP State: dp[i][j] stores the side length of the largest square submatrix with all 1s ending at matrix[i-1][j-1].
• Recurrence Relation: If matrix[i-1][j-1] == 1, then dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j]). Otherwise, dp[i][j] = 0.
• Time Complexity: O(rows \* cols).
• Space Complexity: O(rows \* cols).
• Applications: Image processing, game development, resource allocation, and more.