Javascript Coding Test Course, Finding the Largest Square

Hello! In this article, we will take a detailed look at how to solve the “Maximum Square” problem using JavaScript. This problem can be efficiently solved using a Dynamic Programming approach. It is a type of problem frequently encountered in coding tests at actual companies, so by solving this problem, we will solidify our understanding of the concept of dynamic programming and explore its application in real-world scenarios.

Problem Description

Given a 2-dimensional array matrix, the problem is to find the length of the side of the largest square made up entirely of ‘1’s. For example, if the input matrix is as follows:

In this matrix, the length of the side of the largest square is 2. In other words, the maximum size of ‘1’s is 2×2.

Approach to Solve the Problem

This problem can be approached in several ways, but using dynamic programming is the most efficient. By using dynamic programming, we can reuse previously calculated values to reduce unnecessary computations. Here is a step-by-step approach to solving this problem.

Step 1: Set Up the Dynamic Programming Table

First, create a 2-dimensional array dp with the same size as the original matrix. This array will store the maximum side length of the square made up of ‘1’s at each position.

Step 2: Handle Boundary Conditions

The first row and the first column of the matrix are set as boundary conditions. In this case, if the position is ‘1’, the maximum side length of the square is 1. If it is ‘0’, there can be no square, so it is set to 0.

Step 3: Fill the DP Array

Next, traverse the matrix and update the DP array based on the value at each position. If the current position matrix[i][j] is ‘1’, the length of the side of the square at that position is calculated as follows:

dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;

Here, the Math.min() function calculates the minimum value from above, left, and diagonal-left. This minimum value represents the minimal length needed to form a square.

Step 4: Process the Result

Finally, to find the side length of the square, look for the largest value in the DP array.

Algorithm Implementation

Now, let’s implement the actual algorithm using JavaScript based on the approach described above.

function maximalSquare(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
    let maxSide = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1; // For the first column or row, it is 1
                } else {
                    dp[i][j] = 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; // Return the area of the square
}

Performance and Complexity Analysis

The time complexity of this algorithm is O(m*n), and the space complexity is O(m*n). Here, m is the number of rows in the matrix, and n is the number of columns. Since a DP array is used, additional space is needed, but this can be optimized to O(n).

Optimization: Reducing Space Complexity

In some cases, the space complexity of the DP array can be reduced to O(n). Two arrays can be used to save the previous DP array, and only the previous state is needed when updating the current state.

function maximalSquare(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    let dp = Array(cols).fill(0);
    let maxSide = 0, prev = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            let temp = dp[j]; // Store the previous value
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[j] = 1;
                } else {
                    dp[j] = Math.min(dp[j], dp[j-1], prev) + 1;
                }
                maxSide = Math.max(maxSide, dp[j]);
            } else {
                dp[j] = 0; // Set to 0 for '0'
            }
            prev = temp; // Update the previous value
        }
    }

    return maxSide * maxSide; // Return the area of the square
}

Conclusion

Today, we learned how to solve the “Maximum Square” problem, which frequently appears in JavaScript coding tests, using dynamic programming. This problem helps to understand the basic concepts of dynamic programming and will greatly enhance your coding skills in real-world scenarios. Don’t forget to improve your understanding of algorithms and data structures by solving various problems!

We will cover more algorithmic problems in the future, so please stay tuned. Thank you!