Program Explanation

The problem at hand is to find the largest square sub-matrix in a binary matrix that contains only 1s.
The solution will use a dynamic programming approach to efficiently compute the result. The key idea is
to build a DP (Dynamic Programming) table where each entry at position (i, j) represents the side length
of the largest square that can be formed ending at position (i, j) in the original matrix.

The core concept is:

• If the matrix value at (i, j) is 0, then no square can end there, so the DP table entry will be 0.
• If the matrix value at (i, j) is 1, the value at DP[i][j] will be the minimum of the three neighboring
  values (top, left, and top-left diagonal) plus 1.

This allows the program to calculate the largest possible square side dynamically while iterating through the matrix.

Program Structure

• We initialize a DP table with the same dimensions as the input matrix, where each cell is initially set to 0.
• We iterate through the binary matrix and populate the DP table based on the aforementioned rules.
• We keep track of the largest side length found during the iteration.
• Finally, the area of the largest square is the square of the side length.

C++ Program Code

// C++ program to find the largest square of 1s in a binary matrix

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to find the largest square containing only 1s
int findLargestSquare(vector<vector<int>>& matrix) {
    if (matrix.empty()) return 0;

    int rows = matrix.size();
    int cols = matrix[0].size();
    
    // DP table to store the side length of the largest square ending at (i, j)
    vector<vector<int>> dp(rows, vector<int>(cols, 0));
    int maxSide = 0;

    // Iterating through the matrix
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // Only consider positions with a '1' in the original matrix
            if (matrix[i][j] == 1) {
                // If we are in the first row or first column, the largest square is 1
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    // Take the minimum of three neighboring squares and add 1
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                }
                // Update maxSide to hold the maximum side length found so far
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }

    // Return the area of the largest square (side * side)
    return maxSide * maxSide;
}

int main() {
    // Example binary matrix
    vector<vector<int>> matrix = {
        {1, 0, 1, 0, 0},
        {1, 0, 1, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0}
    };

    // Finding and printing the area of the largest square of 1s
    int largestSquareArea = findLargestSquare(matrix);
    cout << "The largest square containing only 1s has an area of: " << largestSquareArea << endl;

    return 0;
}
    

Code Documentation

Function: findLargestSquare()
This function takes a binary matrix as input and returns the area of the largest square containing only 1s.

• matrix: A 2D vector representing the binary matrix.
• dp: A 2D vector that stores the side length of the largest square that ends at each cell.
• maxSide: An integer variable that keeps track of the largest side length found during iteration.

Return Value:
The function returns the area of the largest square (side length squared).

Function: main()
This is the entry point of the program, where we define an example binary matrix and call the findLargestSquare()
function to calculate the largest square of 1s. The result is then printed to the console.

Key Concepts

Dynamic Programming: This approach builds up solutions to smaller subproblems (finding the largest square
at each position in the matrix) and uses those solutions to solve the larger problem (finding the largest square in the entire matrix).

2D Vectors: We use 2D vectors in C++ to represent both the input binary matrix and the DP table.