Hello, and welcome to the coding test problem-solving course using Kotlin. In this session, we will solve the problem called “Finding the Largest Square.” The task is to find the area of the largest square in a given 2D array. Through this problem, you will learn the basic concept of Dynamic Programming and understand the syntax and features of the Kotlin language.
Problem Description
There is a given 2D binary array of size m x n. In this array, ‘1’ indicates that a square can be formed at that position, while ‘0’ indicates it cannot. The goal is to find the area of the largest square.
For example, consider the following array:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
In this case, the area of the largest square is 4. (2×2 square)
Approach to the Problem
To solve this problem, we will use Dynamic Programming. Here are the main steps to solve the problem:
- Initialize DP Array: Create a DP array with the same size as the input 2D array. Each element in this DP array represents the length of the side of the square ending at position (i, j).
- Set State Transition Relation: If grid[i][j] is ‘1’, then DP[i][j] will be the minimum of DP[i-1][j], DP[i][j-1], and DP[i-1][j-1] + 1. This determines the length of the largest square at (i,j).
- Track Maximum Square Side Length: Through this process, track the side length of the largest square and finally calculate the area by squaring that value.
Code Implementation
Now let’s implement the above algorithm in Kotlin. Below is the code for the algorithm:
fun maximalSquare(matrix: Array): Int {
if (matrix.isEmpty()) return 0
val m = matrix.size
val n = matrix[0].size
val dp = Array(m) { IntArray(n) }
var maxSide = 0
for (i in 0 until m) {
for (j in 0 until n) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1 // For the first row or first column
} else {
dp[i][j] = minOf(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
}
maxSide = maxOf(maxSide, dp[i][j])
}
}
}
return maxSide * maxSide // Return the area of the square
}
Code Explanation
The code takes a 2D array as input and calculates the length of the side of the square ending at each cell. Here is an explanation of the key parts of the code:
- Initial Validation: Checks whether the input matrix is empty. If it is, returns 0.
- Double Loop: Iterates through each element, updating the values in the DP table if it is ‘1’.
- Maximum Side Update: Tracks the maximum value at each case and returns the final result by squaring it.
Complexity Analysis
The time complexity of this algorithm is O(m * n), and since it uses a DP array, the space complexity is also O(m * n). However, the space can be optimized. By using two variables instead of a DP array to store the information of the current row and the previous row, the space complexity can be reduced to O(n).
Optional Space Optimization Code
fun maximalSquare(matrix: Array): Int {
if (matrix.isEmpty()) return 0
val m = matrix.size
val n = matrix[0].size
val dp = IntArray(n)
var maxSide = 0
var prev = 0
for (i in 0 until m) {
for (j in 0 until n) {
val temp = dp[j]
if (matrix[i][j] == '1') {
dp[j] = if (i == 0 || j == 0) 1 else minOf(dp[j], dp[j - 1], prev) + 1
maxSide = maxOf(maxSide, dp[j])
} else {
dp[j] = 0
}
prev = temp
}
}
return maxSide * maxSide
}
Conclusion
In this course, we learned how to solve the “Finding the Largest Square” problem. In this process, we understood the basic concepts of Dynamic Programming and learned how to implement algorithms in the Kotlin language. These algorithmic problems will help improve problem-solving skills and greatly assist in preparing for coding tests. In the next session, we will cover another interesting algorithm problem. Thank you!