Problem Description
Given a two-dimensional array, the problem is to find the area of the largest square composed of 1s. Each element of the array can be either 0 or 1, where 1 indicates that the position is filled. For example, consider the following array:
0 1 1 0
1 1 1 1
0 1 1 0
0 1 1 1
In this case, the size of the largest square is 3, and the area is 9.
Input Format
The input is given as a two-dimensional array of size m x n. The value at the i-th row and j-th column in this array represents a cell in the array.
Output Format
Returns the area of the largest square as an integer.
Approach
This problem can be solved using Dynamic Programming. The basic idea of dynamic programming is to use previously computed results to efficiently calculate new results. The process is as follows:
- Create a new two-dimensional DP array. DP[i][j] represents the maximum side length of the square at position (i, j).
- Iterate through the elements of the array, and if matrix[i][j] is 1, DP[i][j] follows the formula:
- However, when i and j are 0, DP[i][j] should be equal to the value of matrix[i][j].
- Keep track of the maximum side length, and use it to calculate the maximum area.
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1
Implementation
public class LargestSquare {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int maxSide = 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1; // First row or first column
} else {
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}
Time Complexity
The time complexity of this algorithm is O(m * n), where m is the number of rows and n is the number of columns. It is very efficient since it iterates through the array once.
Space Complexity
Since a DP array is used, the space complexity is O(m * n). However, we can optimize the space as only the results from the previous row are needed.
Optimization Method
Instead of using a DP array, we can store only the results of one row to reduce the space complexity to O(n). Here is the code with this optimization applied:
public class OptimizedLargestSquare {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int maxSide = 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[] dp = new int[cols + 1];
int prev = 0;
for (int i = 0; i < rows; i++) {
for (int j = 1; j <= cols; j++) {
int temp = dp[j]; // Save current DP[j] value
if (matrix[i][j - 1] == '1') {
dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;
maxSide = Math.max(maxSide, dp[j]);
} else {
dp[j] = 0; // Not 1
}
prev = temp; // Save previous DP[j] value
}
}
return maxSide * maxSide;
}
}
Conclusion
The problem of finding the largest square is a good illustration of the importance of dynamic programming. Through this problem, one can enhance their algorithmic problem-solving skills and practice frequently tested patterns in coding interviews.