221. Maximal Square

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
 

Example 1:

Input: matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
Output: 4

Example 2:

Input: matrix = [[“0”,“1”],[“1”,“0”]]
Output: 1

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is ‘0’ or ‘1’.

From: LeetCode
Link: 221. Maximal Square

---

Solution:

Ideas：

1. Create a two-dimensional array dp of the same size as the input matrix to store the size of the largest square ending at that position.

2. Initialize the first row and first column of dp to be the same as the input matrix since the largest square for these positions can only be 1 if the corresponding input is 1, or 0 otherwise.

3. Iterate through the matrix starting from the second row and second column, and for each 1 encountered, set dp[i][j] to be the minimum of dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] plus 1. This represents the largest square that can be formed ending at that position.

4. Keep track of the maximum size encountered in the dp array as this represents the side length of the largest square.

5. The area of the largest square is the maximum size squared.

Code:

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
    int maxSide = 0; // To keep track of the maximum side length of the square
    // dp array
    int dp[matrixSize][*matrixColSize];
    memset(dp, 0, sizeof(dp)); // Initialize dp array with 0

    // Initialize first row and first column of dp array
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < *matrixColSize; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = matrix[i][j] - '0'; // Convert char to int
            }
            maxSide = max(maxSide, dp[i][j]); // Update maxSide
        }
    }

    // Compute the rest of the dp array
    for (int i = 1; i < matrixSize; i++) {
        for (int j = 1; j < *matrixColSize; j++) {
            if (matrix[i][j] == '1') {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                maxSide = max(maxSide, dp[i][j]); // Update maxSide
            }
        }
    }

    return maxSide * maxSide; // Return the area
}

// Helper function to find the minimum of two numbers
int min(int a, int b) {
    return (a < b) ? a : b;
}

// Helper function to find the maximum of two numbers
int max(int a, int b) {
    return (a > b) ? a : b;
}