Sponsored
Sponsored
In this approach, a dynamic programming (DP) table is used to store the size of the largest square whose bottom-right corner is at each cell. For each cell (i, j) with a value of '1', we check its top (i-1, j), left (i, j-1), and top-left (i-1, j-1) neighbors to determine the size of the largest square ending at (i, j). If any of these neighbors are '0', the square cannot extend to include (i, j). The formula is: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The maximum value in the DP table will be the side length of the largest square, and the area is its square.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n), due to the DP table.
1#include <string.h>
2
3int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
4 if (matrixSize == 0 || *matrixColSize == 0) return 0;
5 int m = matrixSize, n = *matrixColSize;
6 int dp[m+1][n+1];
7 memset(dp, 0, sizeof(dp));
8 int max_side = 0;
9 for (int i = 1; i <= m; ++i) {
10 for (int j = 1; j <= n; ++j) {
11 if (matrix[i-1][j-1] == '1') {
12 dp[i][j] = fmin(fmin(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
13 if (dp[i][j] > max_side) {
14 max_side = dp[i][j];
15 }
16 }
17 }
18 }
19 return max_side * max_side;
20}The C solution uses a two-dimensional array to store the size of potential squares ending at each position. We initialize it with one extra row and column of zeros. The solution iterates the matrix, leveraging boundary padding to avoid extra edge checks, and updates the DP table.
This approach uses a similar DP strategy but optimizes space by utilizing a one-dimensional array instead of a full 2D DP table. The key idea is that while processing the matrix row by row, previous rows' information will be partially redundant. Hence, we can maintain only the current and previous row data in separate arrays or even use a single array with swap states.
Time Complexity: O(m * n)
Space Complexity: O(n)
1public class Solution {
public int MaximalSquare(char[][] matrix) {
if (matrix.Length == 0) return 0;
int m = matrix.Length, n = matrix[0].Length;
int[] prev = new int[n + 1];
int[] current = new int[n + 1];
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
current[j] = Math.Min(Math.Min(prev[j], current[j - 1]), prev[j - 1]) + 1;
maxSide = Math.Max(maxSide, current[j]);
}
}
Array.Copy(current, prev, n + 1);
Array.Clear(current, 0, n + 1);
}
return maxSide * maxSide;
}
}C# utilizes a similar logic with single dimensional `int` arrays for processing, swapping them with each iteration over rows. Utilizing Array.Copy and Array.Clear to manage elements over iterations.