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:<\/p>\n
\n 0 1 1 0\n 1 1 1 1\n 0 1 1 0\n 0 1 1 1\n <\/pre>\nIn this case, the size of the largest square is 3, and the area is 9.<\/p>\n
Input Format<\/h2>\n
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.<\/p>\n
Output Format<\/h2>\n
Returns the area of the largest square as an integer.<\/p>\n
Approach<\/h2>\n
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:<\/p>\n
\n
- Create a new two-dimensional DP array. DP[i][j] represents the maximum side length of the square at position (i, j).<\/li>\n
- Iterate through the elements of the array, and if matrix[i][j] is 1, DP[i][j] follows the formula:<\/li>\n
DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1<\/pre>\n- However, when i and j are 0, DP[i][j] should be equal to the value of matrix[i][j].<\/li>\n
- Keep track of the maximum side length, and use it to calculate the maximum area.<\/li>\n<\/ol>\n
Implementation<\/h2>\n
\n\npublic class LargestSquare {\n public int maximalSquare(char[][] matrix) {\n if (matrix == null || matrix.length == 0) return 0;\n \n int maxSide = 0;\n int rows = matrix.length;\n int cols = matrix[0].length;\n int[][] dp = new int[rows][cols];\n \n for (int i = 0; i < rows; i++) {\n for (int j = 0; j < cols; j++) {\n if (matrix[i][j] == '1') {\n if (i == 0 || j == 0) {\n dp[i][j] = 1; \/\/ First row or first column\n } else {\n dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;\n }\n maxSide = Math.max(maxSide, dp[i][j]);\n }\n }\n }\n \n return maxSide * maxSide;\n }\n}\n<\/code>\n <\/pre>\nTime Complexity<\/h2>\n
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.<\/p>\n
Space Complexity<\/h2>\n
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.<\/p>\n
Optimization Method<\/h2>\n
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:<\/p>\n
\n\npublic class OptimizedLargestSquare {\n public int maximalSquare(char[][] matrix) {\n if (matrix == null || matrix.length == 0) return 0;\n\n int maxSide = 0;\n int rows = matrix.length;\n int cols = matrix[0].length;\n int[] dp = new int[cols + 1];\n int prev = 0;\n\n for (int i = 0; i < rows; i++) {\n for (int j = 1; j <= cols; j++) {\n int temp = dp[j]; \/\/ Save current DP[j] value\n if (matrix[i][j - 1] == '1') {\n dp[j] = Math.min(Math.min(dp[j], dp[j - 1]), prev) + 1;\n maxSide = Math.max(maxSide, dp[j]);\n } else {\n dp[j] = 0; \/\/ Not 1\n }\n prev = temp; \/\/ Save previous DP[j] value\n }\n }\n\n return maxSide * maxSide;\n }\n}\n<\/code>\n <\/pre>\nConclusion<\/h2>\n
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.<\/p>\n