Example: Maximum Size Square Submatrix in C++

// 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;
}