Java Coding Test Course, Finding the Largest Square

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:

1. Create a new two-dimensional DP array. DP[i][j] represents the maximum side length of the square at position (i, j).
2. Iterate through the elements of the array, and if matrix[i][j] is 1, DP[i][j] follows the formula:

DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1

3. However, when i and j are 0, DP[i][j] should be equal to the value of matrix[i][j].
4. Keep track of the maximum side length, and use it to calculate the maximum area.

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.