Algorithm problems play an important role in developing problem-solving skills for programmers. In this article, we will address the problem of finding the largest square using Swift. The goal is to find the area of the largest square in a given 2D array.
Problem Description
Given a binary matrix, write a function to find the largest square containing only 1s and return its area. 0 represents an empty cell, and 1 represents a filled cell.
Example
Input:
[
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0]
]
Output: 4
Problem Solving Process
Approach to the Problem
To solve this problem, we will use a dynamic programming approach. Below are the steps to tackle the problem.
- Create a DP table based on the given binary matrix.
- Calculate the size of the largest square at each cell.
- More specifically, while traversing each element of the matrix, if that element is 1, update it to be the minimum value of the element to the right, below, and diagonally below plus one.
- Calculate and return the area of the largest square found.
Dynamic Programming Table Construction
The size of the DP table will be the same as the input matrix, and the values at each element will be set according to the following rules.
- If it is 0: Set to 0 since no square can be formed at that position.
- If it is 1: Calculate the size of the square by referencing the adjacent values as described above.
Swift Code Implementation
Now let’s implement the approach described above in Swift code.
func maximalSquare(_ matrix: [[Character]]) -> Int {
guard !matrix.isEmpty else { return 0 }
let rows = matrix.count
let cols = matrix[0].count
var dp = Array(repeating: Array(repeating: 0, count: cols), count: rows)
var maxSide = 0
for i in 0..<rows {="" for="" j="" in="" 0..<cols="" if="" i="=" 0="" ||="" dp[i][j]="matrix[i][j]" =="1" ?="" 1="" :="" }="" else="" matrix[i][j]="=" "1"="" dp[i][j-1],="" dp[i-1][j-1])="" +="" maxside="max(maxSide," dp[i][j])="" return="" *="" <="" code=""></rows>
<h3>Code Explanation</h3>
<p>Let me explain all the variables used in the code above:</p>
<ul>
<li><strong>rows</strong>: The number of rows in the matrix</li>
<li><strong>cols</strong>: The number of columns in the matrix</li>
<li><strong>dp</strong>: The dynamic programming table storing the size of each square</li>
<li><strong>maxSide</strong>: The length of the side of the largest square found so far</li>
</ul>
<h3>Test Cases</h3>
<p>Now let's test the code we wrote. Below are some test cases.</p>
<pre><code>
let testMatrix1: [[Character]] = [
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
]
let result1 = maximalSquare(testMatrix1)
print(result1) // 4
let testMatrix2: [[Character]] = [
["0", "1"],
["1", "0"]
]
let result2 = maximalSquare(testMatrix2)
print(result2) // 1
</code></pre>
<h3>Conclusion</h3>
<p>In this tutorial, we learned how to solve the problem of finding the largest square using Swift. This problem can be efficiently solved through the application of dynamic programming and is commonly encountered in coding interviews. Solving real algorithm problems is very beneficial, and I hope that through practice, you can elevate your problem-solving skills to the next level.</p>
<h2>References</h2>
<p>If you want to learn more about this problem in depth, please refer to the following resources:</p>
<ul>
<li><a href="https://www.geeksforgeeks.org/largest-square-formed-in-a-matrix/" target="_blank" rel="noopener">Largest Square Formed in a Matrix - GeeksforGeeks</a></li>
<li><a href="https://leetcode.com/problems/maximal-square/" target="_blank" rel="noopener">Maximal Square - LeetCode</a></li>
<li><a href="https://medium.com/swlh/understanding-dynamic-programming-with-maximum-square-14eb7d9f6548" target="_blank" rel="noopener">Understanding Dynamic Programming with Maximum Square - Medium</a></li>
</ul>
<p></p>
<div id="jp-relatedposts" class="jp-relatedposts">
<h3 class="jp-relatedposts-headline"><em>관련</em></h3>
</div>