One of the common problems that often appears in coding tests is finding the largest square in a two-dimensional array. This problem can be defined as follows.
Problem Definition
Given a binary matrix (a two-dimensional array consisting of 0s and 1s), find the area of the largest square composed of 1s.
For example, let’s assume we have the following matrix.
[
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0]
]
In the matrix above, the largest square is the area from (1, 1) to (3, 3), with an area of 9.
Problem Approach and Solution Process
To solve this problem, we can use the Dynamic Programming method. This methodology breaks the problem down into smaller subproblems and uses the results to derive the final outcome.
Approach Using Dynamic Programming
1. First, we will get the size of the given matrix and define a 2D array dp for dynamic programming. Each element of this dp array will represent the length of one side of the largest square at a specific position.
2. Initialization: Initialize each element of the dp array to 0. However, the first row and first column of the given matrix should be set to 1 only for positions in the original matrix where there is a 1.
3. Filling the dp array: By examining each element of the binary matrix, if the value at a specific position (i, j) is 1, then dp[i][j] is set to the minimum of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] plus 1. This is how we calculate the sides of the largest square.
4. Result: We need to find the largest value in the dp array, and the square of this value will be the area of the square we are looking for.
Implementation of Dynamic Programming
Now, let’s write a Python code based on the above method.
def maximalSquare(matrix):
if not matrix:
return 0
max_square_len = 0
rows = len(matrix)
cols = len(matrix[0])
dp = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_square_len = max(max_square_len, dp[i][j])
return max_square_len * max_square_len
Code Explanation
The first line of the code checks whether the given matrix is empty. If it is empty, the result is 0.
Next, it retrieves the number of rows and columns in the matrix and creates the dp array. This array has the same size as the given binary matrix and is initialized to 0.
Using a loop, we iterate through each element, processing only when the current element is 1. During this process, we fill the dp array using the previously mentioned relationships. Here, we always track and update the length of the largest square’s side.
Finally, we return the area of the largest square.
Complexity Analysis
The above algorithm has a time complexity of O(n * m), where n is the number of rows in the matrix and m is the number of columns. The space complexity is O(n * m), which is the space needed to store the dp array.
Let’s Try with an Example
Now, let’s use this function to find the largest square in the given matrix.
matrix = [
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
]
print(maximalSquare(matrix)) # 9
Conclusion
This problem is one of the frequently encountered types in coding tests. If you can understand and solve this problem well through practice, it will greatly help you to solve similar problems. Moreover, the ability to understand and apply the principles of dynamic programming is useful for solving various algorithmic problems.
Additionally, you can also tackle more complex variations of this problem by extending the binary matrix into more intricate forms. For example, there are various types of problems where the structure of 0s and 1s changes in the given matrix, or where you need to find different shapes of squares or rectangles that satisfy given conditions.
Moving Forward
Continue to practice solving more algorithm problems and optimizing by considering time complexity, space complexity, and so on. Deepening your understanding of frequently used data structures and algorithms is also very important. Furthermore, as you encounter various problems, your problem-solving skills will naturally improve.
We hope to help you grow your coding skills through many algorithm courses in the future!